Oppdager sykliske spillelister i JavaScript
Å finne sykluser eller repetisjoner er et vanlig problem mens du svarer på kodende intervjuspørsmål, spesielt de som krever datastrukturer som koblede lister. Dette problemet oppstår vanligvis i spillelister, der sanger kan kobles til hverandre i en kjede av referanser. En spilleliste sies å være repeterende hvis en sang refererer til en tidligere sang.
Målet med denne JavaScript-kodingsøvelsen er å skrive en funksjon som bestemmer om noen sanger i en spilleliste skal gjentas. Dette går over hver sang en etter en og ser om det er en referanse som går tilbake til en tidligere sang. Selv erfarne programmerere kan snuble over subtilitetene ved objektreferanser og sløyfekontroll mens de prøver å løse dette tilsynelatende enkle problemet i JavaScript.
Ofte stammer problemet fra måten iterasjonslogikken uttrykkes på, spesielt fra måten referanser mellom objekter håndteres på. I dette tilfellet avhenger løsningen av din evne til å forstå hvordan JavaScript administrerer objektreferanser inne i løkker. Vi vil konsentrere oss om hvordan vi på riktig måte kan tildele og spore disse referansene i en spilleliste mens vi undersøker løsningen.
Vi vil dissekere problemet i detalj, se på manglene ved den eksisterende løsningen og tilby en brukbar løsning på denne gjentatte spillelistehindringen i diskusjonen som følger. Med denne løsningen vil funksjonen kunne gjenkjenne sykliske referanser i en spilleliste nøyaktig og produsere det tiltenkte resultatet.
| Kommando | Eksempel på bruk |
|---|---|
| Set() | JavaScript Set()-objekt brukes til å lagre unike data. For å hjelpe med å identifisere spillelistesykluser, brukes den i eksemplet til å spore sanger som vises, og sørge for at ingen sang spilles av igjen. |
| has() | Set()-objektet har funksjonen has(). Den sjekker om et spesifikt element finnes i settet. Her sjekker den om en sang allerede er hørt, noe som indikerer at spillelisten gjentas. |
| add() | Set()-objektet har funksjonen has(). Den tester om et gitt element eksisterer i settet. Her sjekker den om en sang allerede er hørt, noe som indikerer at spillelisten gjentas. |
| two-pointer technique | Denne metoden, som noen ganger blir referert til som Floyd-Warshall-syklusdeteksjonsalgoritmen, navigerer i spillelisten ved å bruke to pekere: sakte og rask. For effektivt å oppdage løkker, beveger den langsomme pekeren seg ett trinn mens den raske pekeren går to trinn. |
| nextSong | Song-klassen har en unik egenskap kalt nextSong som refererer til sangen som kommer etter den på spillelisten. Det muliggjør imitasjon av en koblet listestruktur der hver sang sekvensielt refererer til annenhver sang. |
| describe() | Mokka-testrammeverkets describe()-funksjon brukes til å organisere relaterte enhetstester. Den deler testene inn i logiske kategorier, slike spillelister som gjentar seg og de som ikke gjør det. |
| it() | I Mocha kalles en testcasedefinisjon det(). Det indikerer et spesifikt tilfelle som må testes, slik at funksjonen gjenkjenner en gjentakende spilleliste på riktig måte. |
| assert.strictEqual() | Denne metoden er fra assert-modulen i Node.js. I dette tilfellet verifiserer den det forutsagte resultatet av spillelisterepetisjonsfunksjonen ved å bestemme om to verdier er strengt tatt like. |
Forstå Playlist Cycle Detection i JavaScript
Det første skriptet som tilbys bruker en koblet listetilnærming for å identifisere sanger som gjentas i en spilleliste ved å betrakte hver sang som en node. JavaScripts klassestruktur brukes til å konstruere en Sang objekt som etterligner flyten av en spilleliste fra spor til spor ved å lagre sangens navn og en referanse til neste sang. Hovedkomponenten i løsningen sporer tidligere møtt musikk ved hjelp av en Sett. Vi bruker en while-løkke for å iterere gjennom sangene, og sjekke om den gjeldende sangen har blitt hørt før. I så fall indikerer vi at spillelisten gjentar seg ved å returnere sann.
Floyds syklusdeteksjonsalgoritme, ofte referert til som to-pekerteknikken, brukes på den andre måten. Ved å bruke denne metoden beveger to pekere seg gjennom spillelisten med separate hastigheter: en hopper over to sanger og flytter frem en sang om gangen. Disse pekerne vil til slutt møtes hvis det er en syklus, noe som indikerer at spillelisten gjentas. Fordi det ikke er nødvendig å lagre sangene som blir sett, er denne metoden mer plasseffektiv og er derfor et bedre alternativ for større spillelister.
Disse løsningene viser også hvordan du oppretter koblede lister i JavaScript fordi neste sang eiendom lenker hver Sang objekt til en annen. Syklusdeteksjon i det første skriptet drar fordel av en settstruktur. Fordi sett sikrer unikhet, kan vi umiddelbart finne ut om en sang allerede er spilt når den er lagt til settet. Dette gjør settene spesielt nyttige. Dette hjelper oss å gjenkjenne når en syklus begynner og hindrer oss i å bli fanget i en endeløs løkke.
Til slutt garanterer enhetstestene som er inkludert for begge strategiene at løsningen er nøyaktig i ulike settinger. For å sjekke koden vår brukte vi Mocha-testrammeverket. Node.js hevde modul brukes for å bekrefte at utgangene er som forventet, og Mocha's beskrive og den funksjoner brukes til å strukturere testene logisk. Enhetstester spiller en avgjørende rolle i utviklingsprosessen siden de validerer at funksjonen fungerer som forventet for både tilbakevendende og ikke-repeterende spillelister, og gir sikkerhet om løsningens motstandskraft.
Oppdager gjentatte sanger i en spilleliste med JavaScript
Objektorientert programmering i JavaScript med While Loops
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
Alternativ tilnærming: Bruk av to pekere for syklusdeteksjon
Deteksjon av koblet listesyklus med Floyd-Warshall-algoritmen
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
Enhetstesting for gjenkjenning av spillelistesløyfe
Tester isRepeatingPlaylist-funksjonen med Node.js og 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);});});
Avanserte spilleliste-løkkedeteksjonsteknikker i JavaScript
Forstå en spillelistes grunnleggende struktur i form av koblede lister er en interessant del av deteksjon av spillelistesløyfer. Hver sang på en ikke-repeterende spilleliste lenker til den før den, til det ikke er flere referanser til den sangen og listen avsluttes. Vi starter en syklus når en sang refererer tilbake til en tidligere, derfor er listen på en måte "uendelig". Å finne denne typen sykluser er viktig ikke bare for spillelister, men også for minneallokering og rutingalgoritmer.
Disse syklusene kan effektivt oppdages i JavaScript ved å bruke pekerteknikker og strukturer som Sett. Fordi det sikrer unikhet og forhindrer at sanger blir besøkt på nytt uten å starte en syklus Sett er spesielt nyttig. Omvendt er Floyd-Warshall to-peker-tilnærmingen en plassoptimalisert løsning der to bevegelige referanser, eller pekere, har forskjellige hastigheter. Hvis de kommer sammen, blir et mønster funnet.
Ved å gjøre disse algoritmene mer effektive, er det mulig å undersøke spillelister som inneholder tusenvis av sanger raskt. To-pekerteknikken er perfekt for situasjoner der minneutnyttelse er et problem fordi den har en O(n)-tidskompleksitet og en O(1)-romkompleksitet. Videre er løsningene våre verifisert til å fungere ordentlig ved å bruke enhetstester, for eksempel de som er laget med Mocha, som oppdager looping og non-looping spillelister i en rekke innstillinger.
Vanlige spørsmål om Playlist Cycle Detection
- Hva er en syklus i en spilleliste?
- Når en sang i spillelisten refererer til en tidligere sang, opprettes en looping-sekvens kjent som en syklus.
- Hvordan oppdager to-pekerteknikken en syklus?
- En rask peker beveger seg to trinn, og en langsom peker beveger seg ett trinn av gangen ved å bruke to-pekerteknikken. Hvis de kommer sammen, er en løkke til stede.
- Hvorfor er en Set brukes til syklusdeteksjon?
- I en Set, lagres distinkte verdier. Det er nyttig å notere musikk som er lyttet til. En loop identifiseres hvis en musikk spilles på nytt.
- Kan jeg bruke denne algoritmen for andre applikasjoner?
- Mye arbeid går faktisk med å identifisere løkker i koblede lister, minneadministrasjon og nettverksruting ved å bruke syklusdeteksjonsteknikken.
- Hvorfor bruker vi while løkker i spillelistetraversering?
- Vi kan iterativt gå gjennom spillelisten ved å bruke while løkke til vi enten finner en syklus eller kommer til slutten av listen.
Siste tanker om å oppdage gjentatte spillelister
Det kan være vanskelig å identifisere sykluser i en spilleliste, spesielt når du navigerer i JavaScripts objektreferanseadministrasjon. Vi kan imidlertid håndtere dette problemet effektivt og strømlinjeforme koden vår ved å bruke teknikker som å bruke to-pekerteknikken eller spore sangreferanser med et sett.
Å vite hvordan disse teknikkene fungerer, vil hjelpe deg med å løse problemer mer effektivt, enten du takler dette for et kodeintervju eller for praktisk bruk. Bruke effektive strukturer som Sett og forstå hvordan pekere som hjelper til med syklusdeteksjon er de viktigste lærdommene man kan lære.
Ressurser og referanser for registrering av spillelistesyklus
- Inspirasjon til algoritmer for gjenkjenning av spillelistesykluser ble hentet fra vanlige problemer med koblede listelister og teknikker som Floyd-Warshall-algoritmen. Lær mer om koblede lister og syklusdeteksjon i denne omfattende ressursen: Syklusdeteksjon på Wikipedia .
- En annen stor ressurs som brukes er JavaScript-dokumentasjonen for Set-objekter, som spiller en nøkkelrolle i den første løsningstilnærmingen: JavaScript satt på MDN .
- For mer detaljerte testteknikker i JavaScript, var Mochas offisielle dokumentasjon en nøkkelkilde for å forstå teststrukturering og påstander: Mokka Testing Framework .
- Utforsk denne veiledningen om to-peker-teknikken, som ofte brukes for syklusdeteksjonsproblemer og er en av de effektive metodene som brukes her: Oppdag sløyfe i en koblet liste .