Pasikartojančių dainų radimas grojaraštyje: kodavimo problemos sprendimas „JavaScript“.

Ciklinių grojaraščių aptikimas „JavaScript“.

Ciklų ar pakartojimų paieška yra dažna problema atsakant į kodavimo interviu klausimus, ypač tuos, kuriems reikia duomenų struktūrų, pvz., susietų sąrašų. Ši problema dažniausiai iškyla grojaraščiuose, kur dainos gali susieti viena su kita nuorodų grandinėje. Sakoma, kad grojaraštis pasikartoja, jei dainoje nurodoma ankstesnė daina.

Šio „JavaScript“ kodavimo pratimo tikslas – parašyti funkciją, kuri nustato, ar grojaraščio dainos kartojasi. Tai peržiūri kiekvieną dainą po vieną ir patikrinama, ar yra nuoroda, kuri grįžta į ankstesnę dainą. Net patyrę programuotojai gali suklupti dėl objektų nuorodų ir kilpos valdymo subtilybių, bandydami išspręsti šią, atrodytų, paprastą „JavaScript“ problemą.

Dažnai problema kyla dėl to, kaip išreiškiama iteracijos logika, ypač dėl to, kaip tvarkomos nuorodos tarp objektų. Šiuo atveju sprendimas priklauso nuo jūsų gebėjimo suprasti, kaip JavaScript tvarko objektų nuorodas kilpų viduje. Nagrinėdami sprendimą sutelksime dėmesį į tai, kaip tinkamai perskirstyti ir sekti šias nuorodas grojaraštyje.

Mes išsamiai išnagrinėsime problemą, pažvelgsime į esamo sprendimo trūkumus ir pasiūlysime veiksmingą šios pasikartojančios grojaraščio kliūties sprendimą tolesnėje diskusijoje. Su šiuo pataisymu funkcija galės tiksliai atpažinti ciklines nuorodas grojaraštyje ir pateikti numatytą rezultatą.

Grojaraščio ciklo aptikimo „JavaScript“ supratimas

Pirmajame siūlomame scenarijuje naudojamas susieto sąrašo metodas, siekiant nustatyti dainas, kurios kartojasi grojaraštyje, kiekvieną dainą laikant mazgu. „JavaScript“ klasės struktūra naudojama konstruoti a Daina objektas, kuris imituoja grojaraščio eigą iš takelio į takelį, išsaugodamas dainos pavadinimą ir nuorodą į kitą dainą. Pagrindinis sprendimo komponentas įrašo anksčiau sutiktą muziką naudojant a Nustatyti. Naudojame ciklą, kad kartotume dainas, patikrindami, ar dabartinė daina buvo girdėta anksčiau. Jei taip, nurodome, kad grojaraštis kartojasi, grąžindami teisingą.

Floydo ciklo aptikimo algoritmas, paprastai vadinamas dviejų žymeklių technika, naudojamas antruoju būdu. Naudojant šį metodą, du rodyklės grojaraštyje juda skirtingu greičiu: vienas praleidžia dvi dainas ir po vieną dainą juda pirmyn. Šios nuorodos galiausiai susitinka, jei yra ciklas, o tai rodo, kad grojaraštis kartojasi. Kadangi nebūtina išsaugoti matomų dainų, šis metodas taupo erdvę, todėl yra geresnis pasirinkimas didesniems grojaraščiams.

Šie sprendimai taip pat parodo, kaip sukurti susietus sąrašus „JavaScript“, nes kita daina nuosavybės nuorodos Daina prieštarauti kitam. Ciklo aptikimas pirmame scenarijuje naudojasi nustatytos struktūros pranašumais. Kadangi rinkiniai užtikrina unikalumą, įtraukę į rinkinį galime akimirksniu nustatyti, ar daina jau grojama. Dėl to rinkiniai yra ypač naudingi. Tai padeda mums atpažinti, kada prasideda ciklas, ir neleidžia patekti į begalinę kilpą.

Galiausiai, abiejų strategijų vienetų testai garantuoja, kad sprendimas yra tikslus įvairiuose nustatymuose. Norėdami patikrinti savo kodą, naudojome Mocha testavimo sistemą. Node.js tvirtinti modulis naudojamas patvirtinti, kad išėjimai yra tokie, kokių tikėtasi, ir Mocha apibūdinti ir tai funkcijos naudojamos logiškai struktūrizuoti testus. Vienetų testai vaidina lemiamą vaidmenį kūrimo procese, nes jie patvirtina, kad funkcija veikia taip, kaip tikėtasi tiek pasikartojantiems, tiek nesikartojantiems grojaraščiams, užtikrinant sprendimo atsparumą.

class Song {
  constructor(name) {
    this.name = name;
    this.nextSong = null;
  }
  /
   * @return {boolean} true if the playlist is repeating, false if not.
   */
  isRepeatingPlaylist() {
    let seenSongs = new Set();
    let current = this;
    while (current) {
      if (seenSongs.has(current)) {
        return true; // Playlist is repeating
      }
      seenSongs.add(current);
      current = current.nextSong;
    }
    return false; // Playlist is not repeating
  }
}
// Testing the solution
let first = new Song("Hello");
let second = new Song("Eye of the Tiger");
let third = new Song("Third");
first.nextSong = second;
second.nextSong = third;
third.nextSong = first; // Creates a loop
console.log(first.isRepeatingPlaylist()); // true

class Song {
  constructor(name) {
    this.name = name;
    this.nextSong = null;
  }
  /
   * @return {boolean} true if the playlist is repeating, false if not.
   */
  isRepeatingPlaylist() {
    let slow = this;
    let fast = this;
    while (fast !== null && fast.nextSong !== null) {
      slow = slow.nextSong; // move slow pointer by 1 step
      fast = fast.nextSong.nextSong; // move fast pointer by 2 steps
      if (slow === fast) {
        return true; // Loop detected
      }
    }
    return false; // No loop
  }
}
// Testing the solution
let first = new Song("Hello");
let second = new Song("Eye of the Tiger");
let third = new Song("Third");
first.nextSong = second;
second.nextSong = third;
third.nextSong = first; // Creates a loop
console.log(first.isRepeatingPlaylist()); // true

const assert = require('assert');
describe('isRepeatingPlaylist', function () {
  it('should return true for a repeating playlist', function () {
    let first = new Song('Song A');
    let second = new Song('Song B');
    let third = new Song('Song C');
    first.nextSong = second;
    second.nextSong = third;
    third.nextSong = first; // Creates a loop
    assert.strictEqual(first.isRepeatingPlaylist(), true);
  });
  it('should return false for a non-repeating playlist', function () {
    let first = new Song('Song A');
    let second = new Song('Song B');
    let third = new Song('Song C');
    first.nextSong = second;
    second.nextSong = third;
    assert.strictEqual(first.isRepeatingPlaylist(), false);
  });
});

Išplėstinė grojaraščio kilpos aptikimo technika „JavaScript“.

Suprasti pagrindinę grojaraščio struktūrą susietus sąrašus yra įdomi grojaraščio ciklo aptikimo dalis. Kiekviena daina nesikartojančiame grojaraštyje susieja su prieš ją esančia daina, kol nebelieka nuorodų į tą dainą ir sąrašas baigiasi. Mes inicijuojame ciklą, kai daina grįžta į ankstesnę, todėl tam tikra prasme sąrašas yra „begalinis“. Tokių ciklų paieška svarbu ne tik grojaraščiams, bet ir atminties paskirstymui bei maršruto parinkimo algoritmams.

Šiuos ciklus galima efektyviai aptikti „JavaScript“, naudojant rodyklės metodus ir struktūras, tokias kaip Nustatyti. Kadangi tai užtikrina unikalumą ir neleidžia pakartotinai peržiūrėti dainų nepradėjus ciklo, Nustatyti yra ypač naudingas. Ir atvirkščiai, Floyd-Warshall dviejų rodyklių metodas yra erdvėje optimizuotas sprendimas, kuriame dvi judančios nuorodos arba rodyklės turi skirtingą greitį. Jei jie susijungia, randamas modelis.

Padarius šiuos algoritmus efektyvesnius, galima greitai peržiūrėti grojaraščius, kuriuose yra tūkstančiai dainų. Dviejų žymeklių technika puikiai tinka tais atvejais, kai atminties panaudojimas yra problema, nes ji turi O(n) laiko sudėtingumą ir O(1) erdvės sudėtingumą. Be to, patikrinta, ar mūsų sprendimai tinkamai veikia, naudojant vienetų testus, pvz., pagamintus naudojant „Mocha“, kurie aptinka grojaraščius su kilpomis ir be kilpų įvairiuose nustatymuose.