Atkārtotu dziesmu atrašana atskaņošanas sarakstā: kodēšanas problēmas atrisināšana JavaScript

Ciklisko atskaņošanas sarakstu noteikšana JavaScript

Ciklu vai atkārtojumu atrašana ir izplatīta problēma, atbildot uz interviju kodēšanas jautājumiem, īpaši tiem, kuriem nepieciešamas datu struktūras, piemēram, saistītie saraksti. Šī problēma parasti rodas atskaņošanas sarakstos, kur dziesmas var būt saistītas viena ar otru atsauču ķēdē. Tiek uzskatīts, ka atskaņošanas saraksts atkārtojas, ja dziesmā ir atsauce uz iepriekšēju dziesmu.

Šī JavaScript kodēšanas uzdevuma mērķis ir uzrakstīt funkciju, kas nosaka, vai atskaņošanas sarakstā tiek atkārtotas dziesmas. Tiek apskatīta katra dziesma pa vienai un noskaidrots, vai ir atsauce, kas atgriežas uz iepriekšējo dziesmu. Pat pieredzējuši programmētāji var paklupt uz objektu atsauču un cilpas kontroles smalkumiem, mēģinot atrisināt šo šķietami vienkāršo problēmu JavaScript.

Bieži vien problēma rodas no tā, kā tiek izteikta iterācijas loģika, jo īpaši no tā, kā tiek apstrādātas atsauces starp objektiem. Šajā gadījumā risinājums ir atkarīgs no jūsu spējas saprast, kā JavaScript pārvalda objektu atsauces cilpu iekšpusē. Pārbaudot risinājumu, mēs koncentrēsimies uz to, kā pareizi atkārtoti piešķirt un izsekot šīs atsauces atskaņošanas sarakstā.

Mēs detalizēti izpētīsim šo problēmu, apskatīsim esošā risinājuma trūkumus un turpmākajā diskusijā piedāvāsim praktiski izmantojamu risinājumu šim atkārtojamajam atskaņošanas saraksta šķērslim. Izmantojot šo labojumu, funkcija varēs precīzi atpazīt cikliskās atsauces atskaņošanas sarakstā un radīt paredzēto rezultātu.

Pavēli	Lietošanas piemērs
Set()	JavaScript Set() objekts tiek izmantots unikālu datu glabāšanai. Lai palīdzētu noteikt atskaņošanas sarakstu ciklus, tas tiek izmantots piemērā, lai izsekotu skatītās dziesmas, pārliecinoties, ka neviena dziesma netiek atskaņota vēlreiz.
has()	Objektam Set() ir funkcija has(). Tas pārbauda, ​​vai komplektā pastāv konkrēts elements. Šeit tas pārbauda, ​​vai dziesma jau ir dzirdēta, norādot, ka atskaņošanas saraksts atkārtojas.
add()	Objektam Set() ir funkcija has(). Tas pārbauda, ​​vai komplektā pastāv noteiktais elements. Šeit tas pārbauda, ​​vai dziesma jau ir dzirdēta, norādot, ka atskaņošanas saraksts atkārtojas.
two-pointer technique	Šī metode, kas dažkārt tiek saukta par Floida-Voršala cikla noteikšanas algoritmu, pārvietojas atskaņošanas sarakstā, izmantojot divus rādītājus: lēnu un ātru. Lai efektīvi noteiktu cilpas, lēnais rādītājs pārvietojas vienu soli, bet ātrais rādītājs iet divus soļus.
nextSong	Dziesmu klasei ir unikāls rekvizīts nextSong, kas atsaucas uz dziesmu, kas ir pēc tās atskaņošanas sarakstā. Tas ļauj imitēt saistītā saraksta struktūru, kurā katra dziesma secīgi atsaucas uz katru citu dziesmu.
describe()	Mocha testēšanas sistēmas funkcija description() tiek izmantota, lai organizētu saistītos vienību testus. Tas iedala testus loģiskās kategorijās, piemēram, atskaņošanas sarakstos, kas atkārtojas, un tajos, kas neatkārtojas.
it()	Moča valodā testa gadījuma definīciju sauc par to (). Tas norāda uz konkrētu gadījumu, kas ir jāpārbauda, ​​piemēram, pārliecinoties, ka funkcija atbilstoši atpazīst atkārtotu atskaņošanas sarakstu.
assert.strictEqual()	Šī metode ir no Node.js apstiprinājuma moduļa. Šajā gadījumā tas pārbauda paredzamo atskaņošanas saraksta atkārtošanas funkcijas rezultātu, nosakot, vai divas vērtības ir stingri vienādas.

Izpratne par atskaņošanas saraksta cikla noteikšanu JavaScript

Pirmajā piedāvātajā skriptā tiek izmantota saistītā saraksta pieeja, lai identificētu dziesmas, kas atkārtojas atskaņošanas sarakstā, katru dziesmu uzskatot par mezglu. JavaScript klases struktūra tiek izmantota, lai izveidotu a objekts, kas atdarina atskaņošanas saraksta plūsmu no celiņa uz celiņu, saglabājot dziesmas nosaukumu un atsauci uz nākamo dziesmu. Risinājuma galvenā sastāvdaļa ieraksta iepriekš sastapto mūziku, izmantojot a . Mēs izmantojam laika cilpu, lai atkārtotu dziesmas, pārbaudot, vai pašreizējā dziesma ir iepriekš dzirdēta. Ja tā, mēs norādām, ka atskaņošanas saraksts atkārtojas, atgriežot true.

Otrajā veidā tiek izmantots Floida cikla noteikšanas algoritms, ko parasti dēvē par divu rādītāju paņēmienu. Izmantojot šo metodi, divi rādītāji pārvietojas atskaņošanas sarakstā ar atšķirīgu ātrumu: viens izlaiž divas dziesmas un virzās uz priekšu pa vienai dziesmai. Šīs norādes galu galā tiksies, ja ir cikls, norādot, ka atskaņošanas saraksts atkārtojas. Tā kā nav nepieciešams saglabāt skatītās dziesmas, šī metode ir daudz efektīvāka, tāpēc tā ir labāka izvēle lielākiem atskaņošanas sarakstiem.

Šie risinājumi arī parāda, kā izveidot saistītos sarakstus JavaScript, jo īpašuma saites katra iebilst pret otru. Cikla noteikšana pirmajā skriptā izmanto iestatītās struktūras priekšrocības. Tā kā komplekti nodrošina unikalitāti, mēs varam uzreiz noteikt, vai dziesma jau ir atskaņota, kad tā ir pievienota kopai. Tas padara komplektus īpaši noderīgus. Tas palīdz mums atpazīt, kad sākas cikls, un neļauj mums iekļūt nebeidzamā cilpā.

Visbeidzot, vienību testi, kas ir iekļauti abām stratēģijām, garantē, ka risinājums ir precīzs dažādos iestatījumos. Lai pārbaudītu mūsu kodu, mēs izmantojām Mocha testēšanas sistēmu. Node.js modulis tiek izmantots, lai apstiprinātu, ka izvadi ir tādi, kā paredzēts, un Mocha's un funkcijas tiek izmantotas, lai loģiski strukturētu testus. Vienību testiem ir izšķiroša nozīme izstrādes procesā, jo tie apstiprina, ka funkcija darbojas, kā paredzēts, gan atkārtotiem, gan neatkārtotiem atskaņošanas sarakstiem, nodrošinot pārliecību par risinājuma noturību.

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

Uzlabotas atskaņošanas sarakstu cilpas noteikšanas metodes JavaScript

Izpratne par atskaņošanas saraksta pamatstruktūru ir interesanta atskaņošanas saraksta cilpas noteikšanas daļa. Katra dziesma atskaņošanas sarakstā, kas neatkārtojas, ir saistīta ar iepriekšējo dziesmu, līdz vairs nav atsauces uz šo dziesmu un saraksts beidzas. Mēs uzsākam ciklu, kad dziesma atsaucas uz iepriekšējo, tāpēc saraksts savā ziņā ir "bezgalīgs". Šāda veida ciklu atrašana ir svarīga ne tikai atskaņošanas sarakstiem, bet arī atmiņas piešķiršanai un maršrutēšanas algoritmiem.

Šos ciklus var efektīvi noteikt JavaScript, izmantojot rādītāju metodes un struktūras, piemēram, . Tā kā tas nodrošina unikalitāti un novērš dziesmu atkārtotu apskati, neuzsākot ciklu, Iestatīt ir īpaši noderīga. Un otrādi, Floyd-Warshall divu rādītāju pieeja ir telpai optimizēts risinājums, kurā divām kustīgām atsaucēm jeb rādītājiem ir atšķirīgs ātrums. Ja tie sanāk kopā, tiek atrasts modelis.

Padarot šos algoritmus efektīvākus, ir iespējams ātri pārbaudīt atskaņošanas sarakstus, kuros ir tūkstošiem dziesmu. Divu rādītāju tehnika ir lieliski piemērota situācijām, kad atmiņas izmantošana ir problēma, jo tai ir O(n) laika sarežģītība un O(1) telpas sarežģītība. Turklāt ir pārbaudīts, vai mūsu risinājumi darbojas pareizi, izmantojot vienību testus, piemēram, tos, kas izveidoti ar Mocha, kas dažādos iestatījumos nosaka atskaņošanas sarakstus ar cilpu un bez cilpas.

1. Kas ir cikls atskaņošanas sarakstā?
2. Ja dziesma atskaņošanas sarakstā atsaucas uz iepriekšēju dziesmu, tiek izveidota cilpas secība, kas pazīstama kā cikls.
3. Kā divu punktu tehnika nosaka ciklu?
4. Ātrs rādītājs pārvieto divus soļus, bet lēns rādītājs pa vienam, izmantojot divu rādītāju paņēmienu. Ja tie sanāk kopā, ir cilpa.
5. Kāpēc ir a izmanto cikla noteikšanai?
6. In a , tiek saglabātas atšķirīgas vērtības. Ir noderīgi sekot līdzi klausītajai mūzikai. Atkārtoti atskaņojot mūziku, tiek identificēta cilpa.
7. Vai es varu izmantot šo algoritmu citām lietojumprogrammām?
8. Patiešām, daudz darba tiek veltīts cilpu identificēšanai saistītajos sarakstos, atmiņas pārvaldībai un tīkla maršrutēšanai, izmantojot cikla noteikšanas paņēmienu.
9. Kāpēc mēs lietojam cilpas atskaņošanas saraksta šķērsošanā?
10. Mēs varam iteratīvi pārlūkot atskaņošanas sarakstu, izmantojot cilpu, līdz atrodam ciklu vai nonākam saraksta beigās.

Atskaņošanas sarakstā var būt grūti noteikt ciklus, jo īpaši, pārvietojoties JavaScript objektu atsauces pārvaldībā. Tomēr mēs varam efektīvi risināt šo problēmu un racionalizēt savu kodu, izmantojot tādas metodes kā divu rādītāju tehnika vai dziesmu atsauču izsekošana ar komplektu.

Zinot, kā šīs metodes darbojas, varēsiet efektīvāk atrisināt problēmas neatkarīgi no tā, vai to risinat kodēšanas intervijai vai praktiskai izmantošanai. Izmantojot efektīvas struktūras, piemēram un izpratne par to, kā norādes palīdz cikla noteikšanā, ir galvenās mācības, kas jāapgūst.