プレイリスト内の繰り返しの曲の検索: 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

代替アプローチ: サイクル検出に 2 つのポインターを使用する

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. 2 ポインター手法を使用すると、速いポインターは 2 ステップ移動し、遅いポインターは 1 ステップずつ移動します。それらが一緒になると、ループが存在します。
5. なぜ Set サイクル検出に使用されますか?
6. で Set、個別の値が保存されます。聴いた音楽をメモしておくと便利です。音楽が再度再生されると、ループが識別されます。
7. このアルゴリズムを他のアプリケーションに使用できますか?
8. 実際、リンク リスト内のループの特定、メモリ管理、およびサイクル検出技術を使用したネットワーク ルーティングには多くの作業が費やされます。
9. なぜ使うのか while プレイリストのトラバーサルでループが発生しますか?
10. を使用してプレイリストを繰り返し処理できます。 while サイクルが見つかるか、リストの最後に到達するまでループします。

繰り返しプレイリストの検出に関する最終的な考え方

特に JavaScript のオブジェクト参照管理をナビゲートする場合、プレイリスト内のサイクルを識別するのは難しい場合があります。ただし、2 ポインター手法を適用したり、セットを使用して曲の参照を追跡したりするなどの手法を採用することで、この問題を効率的に処理し、コードを合理化できます。

これらのテクニックがどのように機能するかを理解すると、コーディング面接で取り組む場合でも、実際の使用で問題に取り組む場合でも、より効果的に問題を解決するのに役立ちます。次のような効果的な構造を使用する セット そして、ポインタがサイクル検出にどのように役立つかを理解することが、学ぶべき主な教訓です。