Otkrivanje cikličkih popisa za reprodukciju u JavaScriptu
Pronalaženje ciklusa ili ponavljanja čest je problem pri odgovaranju na pitanja intervjua za kodiranje, osobito onih koja zahtijevaju strukture podataka poput povezanih popisa. Taj se problem obično javlja na popisima za reprodukciju, gdje se pjesme mogu povezivati jedna s drugom u lancu referenci. Za popis pjesama kaže se da se ponavlja ako se pjesma poziva na prethodnu pjesmu.
Cilj ove vježbe JavaScript kodiranja je napisati funkciju koja određuje hoće li se neke pjesme na popisu za reprodukciju ponavljati. Ovo prolazi svaku pjesmu jednu po jednu i vidi postoji li referenca koja se vraća na prethodnu pjesmu. Čak i iskusni programeri mogu naići na suptilnosti referenci objekata i kontrole petlje dok pokušavaju riješiti ovaj naizgled jednostavan problem u JavaScriptu.
Problem često proizlazi iz načina na koji se izražava logika ponavljanja, posebno iz načina na koji se rukuje referencama između objekata. U ovom slučaju, rješenje ovisi o vašoj sposobnosti da shvatite kako JavaScript upravlja referencama objekata unutar petlji. Dok ispitujemo rješenje, usredotočit ćemo se na to kako prikladno preraspodijeliti i pratiti te reference unutar popisa za reprodukciju.
Detaljno ćemo raščlaniti problem, pogledati nedostatke postojećeg rješenja i ponuditi izvedivo rješenje za ovu prepreku popisa za reprodukciju koja se ponavlja u raspravi koja slijedi. Uz ovaj popravak, funkcija će moći točno prepoznati cikličke reference na popisu za reprodukciju i proizvesti željeni rezultat.
| Naredba | Primjer korištenja |
|---|---|
| Set() | JavaScript Set() objekt se koristi za pohranu jedinstvenih podataka. Kako bi se lakše identificirali ciklusi popisa za reprodukciju, u primjeru se koristi za praćenje pjesama koje se gledaju, osiguravajući da se nijedna pjesma ne reproducira ponovno. |
| has() | Objekt Set() ima funkciju has(). Provjerava postoji li određeni element u skupu. Ovdje provjerava je li pjesma već slušana, što pokazuje da se popis za reprodukciju ponavlja. |
| add() | Objekt Set() ima funkciju has(). Provjerava postoji li dati element u skupu. Ovdje provjerava je li pjesma već slušana, što pokazuje da se popis za reprodukciju ponavlja. |
| two-pointer technique | Ova metoda, koja se ponekad naziva Floyd-Warshallovim algoritmom za otkrivanje ciklusa, kreće se popisom za reprodukciju pomoću dva pokazivača: sporog i brzog. Za učinkovito otkrivanje petlji, spori pokazivač pomiče se jedan korak dok brzi pokazivač ide dva koraka. |
| nextSong | Klasa Song ima jedinstveno svojstvo zvano nextSong koje upućuje na pjesmu koja dolazi nakon nje na popisu za reprodukciju. Omogućuje imitaciju povezane strukture popisa u kojoj svaka pjesma uzastopno upućuje na svaku drugu pjesmu. |
| describe() | Funkcija describe() okvira za testiranje Mocha koristi se za organiziranje povezanih jediničnih testova. Dijeli testove u logične kategorije, popise za reprodukciju koji se ponavljaju i one koji se ne ponavljaju. |
| it() | U Mochi se definicija testnog slučaja naziva it(). Označava specifičan slučaj koji treba testirati, kao što je osiguravanje da funkcija pravilno prepoznaje ponavljajući popis za reprodukciju. |
| assert.strictEqual() | Ova metoda je iz assert modula u Node.js. U ovom slučaju, provjerava predviđeni rezultat funkcije ponavljanja popisa za reprodukciju određivanjem jesu li dvije vrijednosti strogo jednake. |
Razumijevanje detekcije ciklusa popisa za reprodukciju u JavaScriptu
Prva ponuđena skripta koristi pristup povezanog popisa za identifikaciju pjesama koje se ponavljaju na popisu za reprodukciju smatrajući svaku pjesmu čvorom. JavaScriptova struktura klase koristi se za konstrukciju a Pjesma objekt koji oponaša tijek popisa pjesama od zapisa do zapisa pohranjujući naziv pjesme i referencu na sljedeću pjesmu. Glavna komponenta rješenja prati prethodno susrećenu glazbu koristeći a set. Koristimo while petlju za ponavljanje kroz pjesme, provjeravajući je li se trenutna pjesma već čula. Ako je tako, označavamo da se popis za reprodukciju ponavlja vraćanjem true.
Floydov algoritam za detekciju ciklusa, koji se obično naziva tehnika dva pokazivača, koristi se na drugi način. Koristeći ovu metodu, dva pokazivača kreću se kroz popis za reprodukciju različitim brzinama: jedan preskače dvije pjesme i pomiče se jednu po jednu pjesmu naprijed. Ovi će se pokazivači na kraju sresti ako postoji ciklus, što ukazuje da se popis za reprodukciju ponavlja. Budući da ne zahtijeva spremanje pjesama koje se vide, ova je metoda učinkovitija u pogledu prostora i stoga je bolja opcija za veće popise pjesama.
Ova rješenja također pokazuju kako stvoriti povezane popise u JavaScriptu jer sljedeća pjesma imovine poveznice svaki Pjesma prigovarati drugome. Detekcija ciklusa u prvoj skripti koristi prednost postavljene strukture. Budući da setovi osiguravaju jedinstvenost, možemo odmah utvrditi je li pjesma već svirana nakon što je dodana u set. Zbog toga su setovi posebno korisni. To nam pomaže da prepoznamo početak ciklusa i sprječava nas da budemo uhvaćeni u beskrajnu petlju.
Na kraju, jedinični testovi koji su uključeni za obje strategije jamče da je rješenje točno u različitim postavkama. Za provjeru našeg koda upotrijebili smo okvir za testiranje Mocha. Node.js tvrditi modul se koristi za potvrdu jesu li rezultati očekivani i Mochini opisati i to funkcije se koriste za logično strukturiranje testova. Jedinični testovi igraju ključnu ulogu u procesu razvoja budući da potvrđuju da funkcija radi prema očekivanjima i za ponavljajuće i za neponavljajuće popise za reprodukciju, dajući jamstvo o otpornosti rješenja.
Otkrivanje pjesama koje se ponavljaju na popisu za reprodukciju pomoću JavaScripta
Objektno orijentirano programiranje u JavaScriptu s while petljama
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 solutionlet 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 loopconsole.log(first.isRepeatingPlaylist()); // true
Alternativni pristup: korištenje dva pokazivača za detekciju ciklusa
Detekcija ciklusa povezanog popisa s Floyd-Warshallovim algoritmom
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 stepfast = fast.nextSong.nextSong; // move fast pointer by 2 stepsif (slow === fast) {return true; // Loop detected}}return false; // No loop}}// Testing the solutionlet 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 loopconsole.log(first.isRepeatingPlaylist()); // true
Jedinično testiranje za otkrivanje petlje popisa za reprodukciju
Testiranje funkcije isRepeatingPlaylist s Node.js i Mocha
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 loopassert.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 otkrivanja petlje popisa pjesama u JavaScriptu
Razumijevanje temeljne strukture popisa za reprodukciju u smislu povezane liste je zanimljiv dio otkrivanja petlje popisa za reprodukciju. Svaka pjesma na popisu za reprodukciju koji se ne ponavlja povezuje se s onom prije nje, sve dok više nema referenci na tu pjesmu i popis ne završi. Pokrećemo ciklus kada se pjesma odnosi na prethodnu, stoga je popis u određenom smislu "beskonačan". Pronalaženje ovakvih ciklusa važno je ne samo za popise za reprodukciju, već i za algoritme za dodjelu memorije i usmjeravanje.
Ti se ciklusi mogu učinkovito detektirati u JavaScriptu korištenjem tehnika pokazivača i struktura kao što je Set. Budući da osigurava jedinstvenost i sprječava ponavljanje pjesama bez pokretanja ciklusa, set posebno je od pomoći. Suprotno tome, Floyd-Warshallov pristup s dva pokazivača prostorno je optimizirano rješenje u kojem dvije pokretne reference ili pokazivači imaju različite brzine. Ako se spoje, nalazi se uzorak.
Čineći ove algoritme učinkovitijima, moguće je brzo pregledati popise za reprodukciju koji sadrže tisuće pjesama. Tehnika dva pokazivača savršena je za situacije kada je korištenje memorije problem jer ima O(n) vremensku složenost i O(1) prostornu složenost. Nadalje, provjereno je da naša rješenja ispravno funkcioniraju upotrebom jediničnih testova, kao što su oni napravljeni s Mochaom, koji otkrivaju popise za reprodukciju koji se ponavljaju i koji se ne ponavljaju u različitim postavkama.
Često postavljana pitanja o otkrivanju ciklusa popisa za reprodukciju
- Što je ciklus na playlisti?
- Kada se pjesma na popisu za reprodukciju poziva na prethodnu pjesmu, stvara se sekvenca u petlji poznata kao ciklus.
- Kako tehnika dvaju točaka otkriva ciklus?
- Brzi pokazivač se pomiče za dva koraka, a spori se pomiče korak po korak koristeći tehniku dva pokazivača. Ako se spoje, prisutna je petlja.
- Zašto je a Set koristi za otkrivanje ciklusa?
- u a Set, pohranjuju se različite vrijednosti. Korisno je bilježiti glazbu koju ste slušali. Identificira se petlja ako se glazba ponovno pusti.
- Mogu li koristiti ovaj algoritam za druge aplikacije?
- Doista, puno posla ide u identificiranje petlji u povezanim popisima, upravljanje memorijom i mrežno usmjeravanje korištenjem tehnike detekcije ciklusa.
- Zašto koristimo while petlje u obilasku popisa za reprodukciju?
- Možemo iterativno proći kroz popis pjesama koristeći while petlja dok ne pronađemo ciklus ili dok ne dođemo do kraja liste.
Završne misli o otkrivanju popisa za reprodukciju koji se ponavljaju
Moglo bi biti teško identificirati cikluse na popisu za reprodukciju, osobito kada se krećete kroz JavaScript upravljanje referencama na objekte. Međutim, možemo učinkovito riješiti ovaj problem i pojednostaviti naš kod korištenjem tehnika kao što je primjena tehnike dva pokazivača ili praćenje referenci pjesama pomoću skupa.
Poznavanje načina na koji ove tehnike funkcioniraju pomoći će vam da učinkovitije riješite probleme, bez obzira na to rješavate li ih za razgovor o kodiranju ili za praktičnu upotrebu. Korištenje učinkovitih struktura poput set i razumijevanje kako pokazivači pomažu u otkrivanju ciklusa glavne su lekcije koje treba naučiti.
Resursi i reference za detekciju ciklusa popisa za reprodukciju
- Nadahnuće za algoritme za detekciju ciklusa popisa za reprodukciju izvučeno je iz uobičajenih problema povezanih popisa i tehnika poput Floyd-Warshallovog algoritma. Saznajte više o povezanim popisima i otkrivanju ciklusa u ovom opsežnom resursu: Detekcija ciklusa na Wikipediji .
- Još jedan sjajan resurs koji se koristi je JavaScript dokumentacija za Set objekte, koji igraju ključnu ulogu u prvom pristupu rješenju: JavaScript postavljen na MDN .
- Za detaljnije tehnike testiranja u JavaScriptu, službena dokumentacija tvrtke Mocha bila je ključni izvor za razumijevanje strukturiranja testa i tvrdnji: Mocha Testing Framework .
- Istražite ovaj vodič o tehnici dva pokazivača, koja se često koristi za probleme detekcije ciklusa i jedna je od učinkovitih metoda koje se ovdje koriste: Otkrij petlju na povezanom popisu .