Iskanje ponavljajočih se pesmi na seznamu predvajanja: Reševanje težave s kodiranjem v JavaScriptu

Zaznavanje cikličnih seznamov predvajanja v JavaScriptu

Iskanje ciklov ali ponovitev je pogosta težava pri odgovarjanju na vprašanja intervjuja o kodiranju, zlasti tistih, ki zahtevajo podatkovne strukture, kot so povezani seznami. Ta težava se običajno pojavi na seznamih predvajanja, kjer so lahko pesmi med seboj povezane v verigi referenc. Za seznam predvajanja pravimo, da se ponavlja, če se pesem sklicuje na prejšnjo skladbo.

Cilj te vaje kodiranja JavaScript je napisati funkcijo, ki določa, ali se katera koli pesem na seznamu predvajanja ponavlja. To pregleduje vsako pesem eno za drugo in ugotavlja, ali obstaja referenca, ki se vrača na prejšnjo pesem. Celo izkušeni programerji se lahko spotaknejo ob tankosti referenc objektov in nadzora zanke, medtem ko poskušajo rešiti to na videz preprosto težavo v JavaScriptu.

Težava pogosto izhaja iz načina izražanja iteracijske logike, zlasti iz načina obravnavanja referenc med objekti. V tem primeru je rešitev odvisna od vaše sposobnosti razumevanja, kako JavaScript upravlja sklice na objekte znotraj zank. Osredotočili se bomo na to, kako ustrezno prerazporediti in slediti tem sklicem na seznamu predvajanja, ko bomo preučevali rešitev.

Težavo bomo podrobno razčlenili, pogledali pomanjkljivosti obstoječe rešitve in ponudili delujočo rešitev za to ponavljajočo se oviro seznama predvajanja v razpravi, ki sledi. S tem popravkom bo funkcija lahko natančno prepoznala ciklične reference na seznamu predvajanja in ustvarila želeni rezultat.

Razumevanje zaznavanja cikla seznama predvajanja v JavaScriptu

Prvi ponujeni skript uporablja pristop povezanega seznama za prepoznavanje pesmi, ki se ponavljajo na seznamu predvajanja, tako da vsako pesem obravnava kot vozlišče. Struktura razreda JavaScript se uporablja za izdelavo a Pesem predmet, ki posnema tok seznama predvajanja od skladbe do skladbe, tako da shrani ime pesmi in sklic na naslednjo skladbo. Glavna komponenta rešitve sledi glasbi, ki ste jo prej srečali z uporabo a Set. Za ponavljanje pesmi uporabljamo zanko while in preverjamo, ali je bila trenutna pesem že slišana. Če je tako, nakažemo, da se seznam predvajanja ponavlja, tako da vrnemo true.

Floydov algoritem zaznavanja ciklov, običajno imenovan tehnika dveh kazalcev, se uporablja na drugi način. S to metodo se dva kazalca premikata po seznamu predvajanja z različnimi hitrostmi: eden preskoči dve pesmi in se premakne naprej eno pesem naenkrat. Ti kazalci se bodo sčasoma srečali, če obstaja cikel, kar pomeni, da se seznam predvajanja ponavlja. Ker ni treba shranjevati videnih skladb, je ta način prostorsko učinkovitejši in je zato boljša možnost za večje sezname predvajanja.

Te rešitve tudi prikazujejo, kako ustvariti povezane sezname v JavaScriptu, ker nextSong lastninske povezave Pesem nasprotovati drugemu. Zaznavanje cikla v prvem skriptu izkorišča nastavljeno strukturo. Ker nizi zagotavljajo edinstvenost, lahko takoj ugotovimo, ali je pesem že predvajana, ko je dodana v niz. Zaradi tega so kompleti še posebej koristni. To nam pomaga prepoznati, kdaj se cikel začne, in preprečuje, da bi se ujeli v neskončno zanko.

Nazadnje, testi enot, ki so vključeni za obe strategiji, zagotavljajo, da je rešitev točna v različnih nastavitvah. Za preverjanje kode smo uporabili ogrodje za testiranje Mocha. Node.js trditi modul se uporablja za potrditev, da so rezultati v skladu s pričakovanji, in Mocha's opisati in to funkcije se uporabljajo za logično strukturiranje testov. Preizkusi enot igrajo ključno vlogo v razvojnem procesu, saj potrjujejo, da funkcija deluje po pričakovanjih tako za ponavljajoče se kot za neponavljajoče se sezname predvajanja, kar daje zagotovilo o odpornosti rešitve.

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

Napredne tehnike zaznavanja zanke seznama predvajanja v JavaScriptu

Razumevanje osnovne strukture seznama predvajanja v smislu povezani seznami je zanimiv del zaznavanja zanke seznama predvajanja. Vsaka pesem na neponavljajočem se seznamu predvajanja je povezana s tisto pred njo, dokler ni več sklicevanj na to pesem in se seznam konča. Cikel sprožimo, ko se pesem nanaša nazaj na prejšnjo, zato je seznam v nekem smislu "neskončen". Iskanje tovrstnih ciklov ni pomembno le za sezname predvajanja, ampak tudi za algoritme za dodeljevanje pomnilnika in usmerjanje.

Te cikle je mogoče učinkovito zaznati v JavaScriptu z uporabo kazalnih tehnik in struktur, kot je Set. Ker zagotavlja edinstvenost in preprečuje, da bi se pesmi ponovno ogledale brez začetka cikla, je Set je še posebej koristno. Nasprotno pa je Floyd-Warshallov pristop z dvema kazalcema prostorsko optimizirana rešitev, pri kateri imata dve gibljivi referenci ali kazalci različni hitrosti. Če se združijo, se najde vzorec.

Če so ti algoritmi učinkovitejši, je mogoče hitro pregledati sezname predvajanja, ki vsebujejo na tisoče pesmi. Tehnika dveh kazalcev je popolna za situacije, ko je uporaba pomnilnika težava, ker ima O(n) časovno kompleksnost in O(1) prostorsko kompleksnost. Poleg tega je preverjeno, da naše rešitve pravilno delujejo z uporabo enotnih testov, kot so tisti, narejeni z Mocha, ki zaznajo ponavljajoče se in ne ponavljajoče se sezname predvajanja v različnih nastavitvah.