재생 목록에서 반복되는 노래 찾기: JavaScript의 코딩 문제 해결

JavaScript를 사용하여 재생 목록에서 반복되는 노래 감지

While 루프를 사용한 JavaScript의 객체 지향 프로그래밍

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

대체 접근 방식: 주기 감지를 위해 두 포인터 사용

Floyd-Warshall 알고리즘을 사용한 연결 목록 순환 감지

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

재생 목록 루프 감지를 위한 단위 테스트

Node.js 및 Mocha를 사용하여 isRepeatingPlaylist 함수 테스트

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

재생 목록 주기 감지에 대해 자주 묻는 질문

1. 재생목록의 사이클이란 무엇인가요?
2. 재생 목록의 노래가 이전 노래를 참조하면 순환이라는 반복 시퀀스가 ​​생성됩니다.
3. 2포인터 기술은 사이클을 어떻게 감지합니까?
4. 빠른 포인터는 두 단계씩 이동하고 느린 포인터는 두 포인터 기술을 사용하여 한 번에 한 단계씩 이동합니다. 이들이 함께 모이면 루프가 존재합니다.
5. 왜 Set 사이클 감지에 사용됩니까?
6. 에서 Set, 고유한 값이 저장됩니다. 듣는 음악을 메모해 두는 것이 도움이 됩니다. 음악이 다시 재생되면 루프가 식별됩니다.
7. 이 알고리즘을 다른 응용 프로그램에 사용할 수 있습니까?
8. 실제로 주기 감지 기술을 사용하여 연결된 목록, 메모리 관리 및 네트워크 라우팅에서 루프를 식별하는 데 많은 작업이 소요됩니다.
9. 우리는 왜 사용합니까? while 재생 목록 순회에서 루프가 발생합니까?
10. 다음을 사용하여 재생목록을 반복적으로 살펴볼 수 있습니다. while 순환을 찾거나 목록의 끝에 도달할 때까지 반복합니다.

반복 재생 목록 감지에 대한 최종 생각

특히 JavaScript의 개체 참조 관리를 탐색할 때 재생 목록의 주기를 식별하는 것이 어려울 수 있습니다. 그러나 두 포인터 기술을 적용하거나 세트를 사용하여 노래 참조를 추적하는 등의 기술을 사용하면 이 문제를 효율적으로 처리하고 코드를 간소화할 수 있습니다.

이러한 기술이 어떻게 작동하는지 알면 코딩 인터뷰를 위해 문제를 해결하든 실제 사용을 위해 문제를 해결하든 관계없이 문제를 보다 효과적으로 해결하는 데 도움이 됩니다. 다음과 같은 효과적인 구조를 사용합니다. 세트 포인터가 주기 감지에 어떻게 도움이 되는지 이해하는 것이 배워야 할 주요 교훈입니다.