البحث عن الأغاني المتكررة في قائمة التشغيل: حل مشكلة الترميز في JavaScript

الكشف عن قوائم التشغيل الدورية في جافا سكريبت

يعد العثور على الدورات أو التكرارات مشكلة شائعة أثناء الإجابة على أسئلة مقابلة الترميز، خاصة تلك التي تتطلب هياكل بيانات مثل القوائم المرتبطة. تظهر هذه المشكلة عادةً في قوائم التشغيل، حيث يمكن ربط الأغاني ببعضها البعض في سلسلة من المراجع. يُقال إن قائمة التشغيل متكررة إذا كانت الأغنية تشير إلى أغنية سابقة.

الهدف من تمرين ترميز JavaScript هذا هو كتابة دالة تحدد ما إذا كانت أي أغانٍ في قائمة التشغيل مكررة أم لا. يتم ذلك من خلال مراجعة كل أغنية واحدة تلو الأخرى ومعرفة ما إذا كان هناك مرجع يعود إلى أغنية سابقة. حتى المبرمجين المتمرسين قد يتعثرون في التفاصيل الدقيقة لمراجع الكائنات والتحكم في الحلقة أثناء محاولتهم حل هذه المشكلة التي تبدو واضحة في JavaScript.

في كثير من الأحيان، تنبع المشكلة من الطريقة التي يتم بها التعبير عن منطق التكرار، وخاصة من الطريقة التي يتم بها التعامل مع المراجع بين الكائنات. في هذه الحالة، يعتمد الحل على قدرتك على فهم كيفية إدارة JavaScript لمراجع الكائنات داخل الحلقات. سنركز على كيفية إعادة تعيين هذه المراجع وتتبعها بشكل مناسب ضمن قائمة التشغيل أثناء فحصنا للحل.

سنقوم بتحليل المشكلة بالتفصيل، وننظر إلى أوجه القصور في الحل الحالي، ونقدم حلاً عمليًا لعائق قائمة التشغيل المتكررة في المناقشة التالية. من خلال هذا الإصلاح، ستكون الوظيفة قادرة على التعرف على المراجع الدورية في قائمة التشغيل بدقة وتحقيق النتيجة المرجوة.

فهم اكتشاف دورة قائمة التشغيل في JavaScript

يستخدم البرنامج النصي الأول المقدم أسلوب القائمة المرتبطة لتحديد الأغاني التي تتكرر في قائمة التشغيل من خلال اعتبار كل أغنية بمثابة عقدة. يتم استخدام بنية فئة JavaScript لإنشاء ملف أغنية كائن يحاكي تدفق قائمة التشغيل من مسار إلى آخر عن طريق تخزين اسم الأغنية وإشارة إلى الأغنية التالية. المكون الرئيسي للحل يتتبع الموسيقى التي تمت مواجهتها مسبقًا باستخدام ملف تعيين. نحن نستخدم حلقة زمنية لتكرار الأغاني، والتحقق لمعرفة ما إذا كانت الأغنية الحالية قد تم سماعها من قبل. إذا كان الأمر كذلك، فإننا نشير إلى أن قائمة التشغيل تتكرر من خلال إرجاع صحيح.

يتم استخدام خوارزمية الكشف عن دورة فلويد، والتي يشار إليها عادة بتقنية المؤشرين، في الطريقة الثانية. باستخدام هذه الطريقة، يتحرك مؤشران عبر قائمة التشغيل بسرعات منفصلة: يتخطى أحدهما أغنيتين ويتحرك للأمام بأغنية واحدة في كل مرة. ستجتمع هذه المؤشرات في النهاية إذا كانت هناك دورة، تشير إلى تكرار قائمة التشغيل. نظرًا لأنها لا تتطلب حفظ الأغاني التي يتم مشاهدتها، فإن هذه الطريقة أكثر كفاءة في استخدام المساحة وبالتالي فهي خيار أفضل لقوائم التشغيل الأكبر حجمًا.

توضح هذه الحلول أيضًا كيفية إنشاء قوائم مرتبطة في JavaScript نظرًا لأن com.nextSong روابط الملكية لكل منهما أغنية اعتراض على آخر. يستفيد اكتشاف الدورة في البرنامج النصي الأول من بنية المجموعة. نظرًا لأن المجموعات تضمن التفرد، يمكننا على الفور تحديد ما إذا كانت الأغنية قد تم تشغيلها بالفعل بمجرد إضافتها إلى المجموعة. وهذا يجعل المجموعات مفيدة بشكل خاص. وهذا يساعدنا على التعرف على متى تبدأ الدورة ويمنعنا من الوقوع في حلقة لا نهاية لها.

وأخيرًا، تضمن اختبارات الوحدة المضمنة لكلتا الاستراتيجيتين دقة الحل في الإعدادات المختلفة. للتحقق من التعليمات البرمجية الخاصة بنا، استخدمنا إطار اختبار Mocha. العقدة.js تأكيد يتم استخدام الوحدة للتأكد من أن المخرجات كما هو متوقع، وMocha's يصف و هو - هي يتم استخدام الوظائف لهيكلة الاختبارات بشكل منطقي. تلعب اختبارات الوحدة دورًا حاسمًا في عملية التطوير نظرًا لأنها تتحقق من أن الوظيفة تعمل كما هو متوقع لكل من قوائم التشغيل المتكررة وغير المتكررة، مما يوفر ضمانًا بشأن مرونة الحل.

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

تقنيات الكشف عن حلقة قائمة التشغيل المتقدمة في JavaScript

فهم البنية الأساسية لقائمة التشغيل من حيث قوائم مرتبطة يعد جزءًا مثيرًا للاهتمام من الكشف عن حلقة قائمة التشغيل. ترتبط كل أغنية في قائمة التشغيل غير المتكررة بالأغنية التي تسبقها، حتى لا يكون هناك المزيد من الإشارات إلى تلك الأغنية وتنتهي القائمة. نبدأ دورة عندما تشير أغنية ما إلى أغنية سابقة، وبالتالي تكون القائمة "لا نهائية". يعد العثور على هذه الأنواع من الدورات أمرًا مهمًا ليس فقط لقوائم التشغيل ولكن أيضًا لتخصيص الذاكرة وخوارزميات التوجيه.

يمكن اكتشاف هذه الدورات بشكل فعال في JavaScript من خلال استخدام تقنيات وهياكل المؤشر مثل تعيين. لأنه يضمن التفرد ويمنع إعادة النظر في الأغاني دون بدء دورة تعيين مفيد بشكل خاص. على العكس من ذلك، فإن نهج فلويد-وارشال ذو المؤشرين هو حل محسن للمساحة حيث يكون لمرجعين متحركين، أو مؤشرات، سرعات مختلفة. إذا اجتمعوا معا، تم العثور على نمط.

ومن خلال جعل هذه الخوارزميات أكثر كفاءة، من الممكن فحص قوائم التشغيل التي تحتوي على آلاف الأغاني بسرعة. تعتبر تقنية المؤشرين مثالية للمواقف التي يكون فيها استخدام الذاكرة مشكلة لأنها تحتوي على تعقيد زمني O(n) وتعقيد مساحة O(1). علاوة على ذلك، تم التحقق من أن حلولنا تعمل بشكل صحيح من خلال استخدام اختبارات الوحدة، مثل تلك التي تم إجراؤها باستخدام Mocha، والتي تكتشف قوائم التشغيل المتكررة وغير المتكررة في مجموعة متنوعة من الإعدادات.