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

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

نظرة عامة على نمط النافذة المنزلق

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

متى تستخدم نافذة الانزلاق:

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

---

أنواع نهج النوافذ المنزلق

1. نافذة منزلق الحجم الثابت

• ما هو : نافذة ذات حجم ثابت ينزلق عبر الصفيف أو السلسلة مع الحفاظ على حالة تشغيل مثل SUM أو المنتج.
• مثال : ابحث عن الحد الأقصى للمجموع الفرعي للحجم k.

مثال مشكلة : أعطيت مجموعة من الأعداد الصحيحة ورقم k ، ابحث عن الحد الأقصى للمجموع من أي سائق فرعي من الحجم k.

def max_sum_subarray(arr, k):
    # Initialize variables to store the maximum sum and the current window sum.
    max_sum = 0
    window_sum = 0

    # First, calculate the sum of the initial window (first 'k' elements).
    for i in range(k):
        window_sum  = arr[i]

    # Set the max_sum to the initial window's sum.
    max_sum = window_sum

    # Now, slide the window across the array. 
    # Start from the kth element and move until the end of the array.
    for i in range(k, len(arr)):
        # Slide the window by subtracting the element that is no longer in the window 
        # (arr[i - k]) and adding the new element (arr[i]).
        window_sum  = arr[i] - arr[i - k]

        # Update max_sum if the current window sum is greater than the previous max_sum.
        max_sum = max(max_sum, window_sum)

    # Return the maximum sum found.
    return max_sum

توضيح:

• تتم تهيئة نافذة من الحجم k.
• عندما تتحرك النافذة عبر الصفيف ، يتم تحقيق التأثير المنزلق عن طريق طرح العنصر الذي لم يعد في النافذة ويضيف العنصر الجديد الذي يدخل النافذة.
• هذا يحسن المشكلة من نهج القوة الغاشمة لـ O (n*k) إلى o (n) ، لأننا لم نعد بحاجة إلى تلخيص النافذة بأكملها لكل تكرار.

---

2. نافذة انزلاق ديناميكية

• ما هو : يتم استخدام هذا عندما لا يتم إصلاح حجم النافذة. تتوسع النافذة أو تتناسب مع متطلبات المشكلة (مثل تلبية مبلغ أو حالة).
• مثال : ابحث عن أصغر سفر فرعي مع مبلغ أكبر من أو يساوي s.

مثال مشكلة : أعطيت مجموعة من الأعداد الصحيحة ورقم S ، ابحث عن أصغر سفر فرعي متجاورة يكون مجموعه أكبر من أو يساوي s.

  def smallest_subarray_with_sum(arr, S):
    # Initialize variables:
    # window_sum: to store the sum of the current window.
    # min_length: to store the length of the smallest subarray found.
    # window_start: the starting index of the sliding window.
    window_sum = 0
    min_length = float('inf')  # Start with a large number to compare minimum lengths.
    window_start = 0

    # Iterate over the array with window_end being the right boundary of the window.
    for window_end in range(len(arr)):
        # Add the current element to the window_sum.
        window_sum  = arr[window_end]

        # While the current window's sum is greater than or equal to S:
        while window_sum >= S:
            # Calculate the current window size and update min_length if smaller.
            min_length = min(min_length, window_end - window_start   1)

            # Shrink the window from the left by removing the element at window_start.
            window_sum -= arr[window_start]

            # Move the start of the window to the right.
            window_start  = 1

    # If min_length was updated, return it; otherwise, return 0 (meaning no valid subarray was found).
    return min_length if min_length != float('inf') else 0

توضيح:

• تتوسع النافذة عن طريق زيادة Window_end حتى يتجاوز المبلغ أو يساوي s.
• بمجرد تلبية الشرط ، تبدأ النافذة في التعاقد من اليسار (window_start) للعثور على الحد الأدنى لحجم السوس الفرعي.
• هذا النهج فعال لأنه يقلل من المشكلة من O (n^2) إلى o (n) ، عن طريق تجنب عمليات إعادة الحواسب.

---

خطوات لتنفيذ حلول النوافذ المنزلق

1. حدد حدود النافذة : تحتاج إلى تحديد بداية ونهاية النافذة.

2. قم بتعيين حالة أولية : للنوافذ الثابتة ، قم بتهيئة المبلغ/المنتج/الشرط للنافذة الأولى. بالنسبة للنوافذ الديناميكية ، يعتمد الحالة الأولية على هدف المشكلة.

3. حرك النافذة :

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

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

---

أسئلة المقابلة الشائعة باستخدام نافذة منزلق

1. أطول فرعية دون تكرار الأحرف

   • مشكلة : أعطيت سلسلة S ، ابحث عن طول أسطول فرعية دون تكرار الأحرف.
   • نمط : استخدم نافذة انزلاقية ديناميكية للتوسع حتى يتم العثور على حرف مكرر ، ثم تعاقد مع النافذة حتى يتم استيفاء الشرط.

2. الحد الأقصى للمجموع الفرعي للحجم k

   • مشكلة : أعطيت مجموعة من الأعداد الصحيحة و integer k ، ابحث عن الحد الأقصى للمجموع من أي فرع من الحجم k.
   • نمط : استخدم نافذة منزلق بحجم ثابت للحفاظ على مجموع عناصر K وتحديث الحد الأقصى للمجموعة أثناء تحريك النافذة عبر المصفوفة.

3. أصغر سفرًا بمجموع معين

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

---

اختراقات النافذة المنزلق للمقابلات

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

2. استخدم hashmap أو تعيين لنظام التشغيل windows الديناميكية : عند التعامل مع السلاسل الفرعية أو العناصر الفريدة ، استخدم مجموعة لتتبع العناصر في النافذة.

3. ابدأ بالتعبير الغاشم ثم تحسين : في بعض المشكلات ، يمكن أن يساعدك في نهج القوة الغاشمة (مثل التحقق من كل سفر فرعي ممكن) في تصور كيف ستقلل نافذة المنزلقة من العمل غير الضروري.

4. ابحث عن الشروط المثلى

   : إذا كانت المشكلة تحتوي على مكون تحسين (مثل تقليل أو زيادة المبلغ أو الطول) ، فقد تكون النافذة المنزلق مناسبة جيدة.

   خاتمة

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

---

في المقالة التالية ، سنستكشف تقنية

اثنين من تقنية المؤشر

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

ترقبوا الجزء 3!