Esitusloendist korduvate lugude leidmine: JavaScripti kodeerimisprobleemi lahendamine

Tsükliliste esitusloendite tuvastamine JavaScriptis

Tsüklite või korduste leidmine on intervjuu kodeerimise küsimustele vastamisel tavaline probleem, eriti sellistele, mis nõuavad andmestruktuure, näiteks lingitud loendeid. See probleem tekib tavaliselt esitusloendites, kus laulud võivad viidete ahelas üksteisega linkida. Esitusloendit peetakse korduvaks, kui lugu viitab eelmisele loole.

Selle JavaScripti kodeerimisharjutuse eesmärk on kirjutada funktsioon, mis määrab, kas esitusloendis olevaid lugusid korratakse. See vaatab iga laulu ükshaaval üle ja vaatab, kas on viidet, mis pöördub tagasi eelmisele loole. Isegi kogenud programmeerijad võivad komistada objektiviidete ja silmuse juhtimise peensustele, kui nad üritavad seda näiliselt otsest JavaScripti probleemi lahendada.

Sageli tuleneb probleem iteratsiooniloogika väljendamise viisist, eriti sellest, kuidas käsitletakse objektidevahelisi viiteid. Sel juhul sõltub lahendus teie võimest mõista, kuidas JavaScript haldab objektiviiteid tsüklite sees. Lahendust uurides keskendume sellele, kuidas neid viiteid esitusloendis õigesti ümber määrata ja jälgida.

Lahkame probleemi üksikasjalikult, vaatleme olemasoleva lahenduse puudujääke ja pakume järgnevas arutelus sellele korduvale esitusloendi takistusele toimiva lahenduse. Selle paranduse abil suudab funktsioon esitusloendis tsüklilisi viiteid täpselt ära tunda ja anda soovitud tulemuse.

Esitusloendi tsükli tuvastamise mõistmine JavaScriptis

Esimene pakutav skript kasutab esitusloendis korduvate lugude tuvastamiseks lingitud loendi lähenemisviisi, käsitledes iga lugu sõlmena. A konstrueerimiseks kasutatakse JavaScripti klassistruktuuri Laul objekt, mis jäljendab esitusloendi kulgu loolt loole, salvestades loo nime ja viite järgmisele loole. Lahenduse põhikomponent jälgib varem kohatud muusikat, kasutades a Määra. Kasutame lugude itereerimiseks ajasilmust, kontrollides, kas praegust lugu on varem kuuldud. Kui jah, siis näitame, et esitusloend kordub, tagastades väärtuse true.

Floydi tsüklituvastusalgoritmi, mida tavaliselt nimetatakse kahe osuti tehnikaks, kasutatakse teisel viisil. Seda meetodit kasutades liiguvad kaks osutit esitusloendis erineva kiirusega: üks jätab kaks lugu vahele ja liigub ühe loo kaupa edasi. Need näpunäited kohtuvad lõpuks tsükli korral, mis näitab, et esitusloend kordub. Kuna see ei nõua nähtud lugude salvestamist, on see meetod ruumisäästlikum ja seetõttu on see parem valik suuremate esitusloendite jaoks.

Need lahendused näitavad ka seda, kuidas luua JavaScriptis lingitud loendeid, kuna järgmine laul atribuutide lingid Laul teisele vastu vaielda. Tsükli tuvastamine esimeses skriptis kasutab seatud struktuuri eeliseid. Kuna komplektid tagavad unikaalsuse, saame pärast komplekti lisamist koheselt kindlaks teha, kas lugu on juba mängitud. See muudab komplektid eriti kasulikuks. See aitab meil ära tunda, millal tsükkel on algamas, ja hoiab meid ära sattumast lõputusse ahelasse.

Lõpuks tagavad mõlema strateegia jaoks kaasatud ühikutestid, et lahendus on erinevates seadetes täpne. Koodi kontrollimiseks kasutasime Mocha testimisraamistikku. Node.js väita moodulit kasutatakse selleks, et kinnitada, et väljundid on ootuspärased, ja Mocha oma kirjeldada ja seda funktsioone kasutatakse testide loogiliseks struktureerimiseks. Ühikutestidel on arendusprotsessis ülioluline roll, kuna need kinnitavad, et funktsioon toimib ootuspäraselt nii korduvate kui ka mittekorduvate esitusloendite puhul, andes kindluse lahenduse vastupidavuse kohta.

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);
  });
});

Täiustatud esitusloendi silmuse tuvastamise tehnikad JavaScriptis

Esitusloendi põhistruktuuri mõistmine lingitud loendid on esitusloendi silmuse tuvastamise huvitav osa. Iga mittekorduva esitusloendi lugu viitab sellele eelnevale, kuni sellele loole enam viiteid pole ja loend lõpeb. Me algatame tsükli, kui laul viitab varasemale, seega on loend teatud mõttes "lõpmatu". Seda tüüpi tsüklite leidmine on oluline mitte ainult esitusloendite, vaid ka mälu eraldamise ja marsruutimisalgoritmide jaoks.

Neid tsükleid saab JavaScriptis tõhusalt tuvastada, kasutades osutitehnikaid ja struktuure, nagu Määra. Kuna see tagab unikaalsuse ja takistab lugude uuesti läbivaatamist ilma tsüklit käivitamata, Määra on eriti abiks. Seevastu Floyd-Warshalli kahe osutiga lähenemine on ruumi jaoks optimeeritud lahendus, kus kahel liikuval viitel või osutil on erinev kiirus. Kui need kokku tulevad, leitakse muster.

Neid algoritme tõhusamaks muutes on võimalik kiiresti uurida tuhandeid lugusid sisaldavaid esitusloendeid. Kahe osuti tehnika sobib suurepäraselt olukordades, kus mälukasutus on probleem, kuna sellel on O(n) ajaline ja O(1) ruumi keerukus. Lisaks kontrollitakse meie lahenduste nõuetekohast toimimist, kasutades ühikuteste, näiteks Mochaga tehtud teste, mis tuvastavad mitmesugustes seadetes korduvaid ja tsüklita esitusloendeid.