كل شيء عن الأنماط!

بمجرد أن تتعلم الأنماط، يصبح كل شيء أسهل قليلاً! إذا كنت مثلي، فمن المحتمل أنك لا تحب المقابلات التقنية، وأنا لا ألومك، فقد تكون صعبة.

تعد مشكلات المصفوفات من أكثر المشكلات شيوعًا التي ستواجهها في المقابلات. غالبًا ما تتضمن هذه المشكلات العمل مع المصفوفات الطبيعية:

const arr = [1, 2, 3, 4, 5];

ومشاكل السلسلة، والتي هي في الأساس صفائف من الأحرف:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

أحد الأنماط الأكثر شيوعًا لحل مشكلات المصفوفات هي النافذة المنزلقة.

نمط النافذة المنزلقة

يتضمن نمط النافذة المنزلقة مؤشرين يتحركان في نفس الاتجاه، مثل نافذة منزلقة عبر المصفوفة.

متى تستخدمه

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

القاعدة 1: إذا كنت بحاجة إلى العثور على مصفوفة فرعية أو سلسلة فرعية وكانت بنية البيانات عبارة عن مصفوفة أو سلسلة، ففكر في استخدام نمط النافذة المنزلقة.

مثال بسيط

إليك مثال أساسي لتقديم مفهوم المؤشرات في نافذة منزلقة:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l   1;  // Right pointer

    while (r 



لاحظ أن مؤشرات اليسار (L) واليمين (R) ليس من الضروري أن تتحرك في نفس الوقت، ولكن يجب أن تتحرك في نفس الاتجاه.



لن يكون المؤشر الأيمن أدنى من المؤشر الأيسر أبدًا.

دعونا نستكشف هذا المفهوم من خلال مشكلة مقابلة حقيقية.


  
  
  مشكلة العالم الحقيقي: أطول سلسلة فرعية دون تكرار الأحرف


المشكلة: بالنظر إلى سلسلة s، ابحث عن طول أطول سلسلة فرعية دون تكرار الأحرف.

الكلمات الرئيسية: sub-سلسلة، الأطول (الحد الأقصى)


function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right = left) {
            left = hash[str[right]]   1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left   1);
    }

    return longest;
}




لا تقلق إذا بدا الأمر معقدًا، فسنتناوله شيئًا فشيئًا.


let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5




جوهر هذه المشكلة هو العثور على أطول سلسلة فرعية بدون أحرف متكررة.


  
  
  النافذة الأولية: الحجم 0


في البداية، يكون كل من المؤشر الأيسر (L) والمؤشر الأيمن (R) في نفس المكان:


let left = 0;

for (let right = 0; right 





h e l l o w o r l d 
^
^
L
R




ولدينا تجزئة (كائن) فارغة:


let hash = {};




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

من خلال النظر إلى السلسلة، يمكننا أن نقول بصريًا أن العالم هو أطول سلسلة فرعية دون تكرار الأحرف:


h e l l o w o r l d 
          ^        ^   
          L        R




يبلغ طول هذا 5. فكيف نصل إلى هناك؟

دعونا نقسمها خطوة بخطوة:


  
  
  الحالة الأولية




hash = {}

h e l l o w o r l d 
^
^
L
R





  
  
  التكرار 1:


في كل تكرار، نضيف الحرف الموجود أسفل مؤشر R إلى خريطة التجزئة ونزيد:


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);




حاليًا، لا توجد أحرف مكررة في نافذتنا (h وe):


hash = {h: 0}
h e l l o w o r l d 
^ ^
L R





  
  
  التكرار 2:




hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R




الآن، لدينا نافذة جديدة: hel.


  
  
  التكرار 3:




hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R




هنا يصبح الأمر مثيرًا للاهتمام: لدينا حرف l بالفعل في تجزئة لدينا، ويشير R إلى حرف l آخر في السلسلة. هذا هو المكان الذي تأتي فيه عبارة if:


if (hash[str[right]] !== undefined)




إذا كانت علامة التجزئة الخاصة بنا تحتوي على الحرف R الذي يشير إليه، فقد وجدنا نسخة مكررة! النافذة السابقة (hel) هي الأطول لدينا حتى الآن.

 إذن ماذا سنفعل بعد ذلك؟ نقوم بتقليص النافذة من اليسار عن طريق تحريك المؤشر L لأعلى نظرًا لأننا قمنا بالفعل بمعالجة السلسلة الفرعية اليسرى. ولكن إلى أي مدى نتحرك L؟


left = hash[str[right]]   1;




ننقل L إلى ما بعد التكرار مباشرة:


hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R




مازلنا نضيف نسختنا المكررة إلى التجزئة، لذلك سيكون لدى L الآن فهرس 3.


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);





  
  
  الحالة الجديدة: التكرار 4




hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R





  
  
  التكرارات من 4 إلى 6




hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R




عندما يشير R إلى نسخة مكررة أخرى (o)، ننقل L إلى ما بعد أول o مباشرة:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R




نستمر حتى نواجه نسخة مكررة أخرى:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R




 لكن لاحظ أنه خارج النافذة الحالية! بدءًا من ث، 


  
  
  القاعدة 3: تجاهل المعالجة الفرعية x


أي شيء خارج النافذة الحالية ليس له أي صلة، لقد قمنا بمعالجته بالفعل. الرمز الرئيسي لإدارة هذا هو:


if (hash[str[right]] !== undefined && hash[str[right]] >= left)




يضمن هذا الشرط أننا نهتم فقط بالأحرف الموجودة في النافذة الحالية، مع تصفية أي تشويش.


hash[str[right]] >= left




نركز على أي شيء أكبر أو يساوي المؤشر الأيسر


  
  
  التكرار النهائي:




hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R




أعلم أن هذا كان تفصيليًا، ولكن تقسيم المشكلات إلى أنماط أو قواعد أصغر هو أسهل طريقة لإتقانها.


  
  
  في ملخص:

• القاعدة 1: الكلمات الرئيسية في المشكلة (على سبيل المثال، الحد الأقصى والحد الأدنى) هي أدلة. تتعلق هذه المشكلة بالعثور على أطول سلسلة فرعية بدون أحرف متكررة.
• القاعدة 2: إذا كنت بحاجة إلى العثور على عناصر فريدة أو غير متكررة، ففكر في خرائط التجزئة.
• القاعدة 3: ركز على النافذة الحالية — أي شيء خارجها ليس له صلة.

نصائح إضافية:

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

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

المشكلة 2: مجموع أكبر من أو يساوي الهدف

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

/**
 * 
 * @param {Array} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

تذكر، مثل أي شيء في البرمجة، التكرار هو المفتاح! تظهر مشكلات النوافذ المنزلقة طوال الوقت، لذا لا تتردد في البحث عن المزيد من الأمثلة على Google واستمر في التدريب.

سأبقي هذا المقال قصيرًا، ولكن تابعونا - ستتعمق المقالة التالية في نمط المؤشرين والتكرار (الاستعداد لمشاكل الشجرة). سيكون الأمر أكثر صعوبة بعض الشيء!

إذا كنت تريد المزيد من المحتوى الحصري، يمكنك متابعتي على Twitter أو Ko-fi وسأقوم بنشر بعض الأشياء الإضافية هناك!

موارد:

دليل المقابلة الفنية

مصفوفات كود ليت 101