عدّ النوافذ التي تحقق قاعدة
حيلة at-most-K ناقص at-most-(K-1)
عدّ النوافذ التي تحقق قاعدة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
العد بدلًا من القياس
تحتاجون أحيانًا إلى عدّ المصفوفات الفرعية التي تحقق قاعدة معينة، لا إلى إيجاد أطولها. وتحول حيلة صغيرة هذه المسألة إلى عمل سهل باستخدام النافذة المنزلقة. 🔢
تحدي العدد K تمامًا
يُعدّ عدّ المصفوفات الفرعية التي تحتوي على K تمامًا من عنصر أو خاصية معينة أمرًا غير مريح مباشرةً. إذ تستمر الحدود في التغير، مما يصعّب إنشاء نافذة واحدة واضحة.
إعادة صياغة «على الأكثر»
يصبح عدّ المصفوفات الفرعية التي تحتوي على K على الأكثر أسهل بكثير باستخدام نافذة واحدة. فعند توسيع النافذة إلى اليمين، تعطي كل قيمة left صالحة مصفوفة فرعية تُعدّ.
حيلة الطرح
العدد الذي يساوي K تمامًا هو atMost(K) ناقص atMost(K - 1). وبذلك ندمج عدّين سهلين للحصول على العدد الصعب الذي نريده فعلًا.
answer = at_most(k) - at_most(k - 1)أنشئوا الدالة المساعدة
اكتبوا دالة واحدة تعدّ المصفوفات الفرعية التي تحتوي على k على الأكثر. فهي تحرّك نافذة وتصغّرها كلما تجاوز العدد k.
def at_most(k):
left = 0
total = 0صغّروا النافذة عند خرق الشرط
وسّعوا النافذة إلى اليمين وحدّثوا حالتها. وما دامت تحتوي على أكثر من k، حرّكوا left إلى الأمام لإعادتها إلى النطاق المسموح.
while count > k:
# remove a[left]
left += 1أضيفوا عدد النوافذ
بعد إصلاح النافذة، تكون كل مصفوفة فرعية تنتهي عند right ويبدأ نطاقها من left أو بعده صالحة. أضيفوا right ناقص left زائد واحد.
total += right - left + 1لماذا ينجح هذا العد
عند تثبيت right، تكون مواضع البداية الصالحة هي left وleft+1 وصولًا إلى right. وهذا يساوي تمامًا right - left + 1 مصفوفة فرعية، تحقق جميعها شرط «على الأكثر k».
ادمجوا الاستدعاءين
شغّلوا الدالة المساعدة مرتين ثم اطرحوا النتيجتين. فكلفة كل استدعاء هي O(n)، لذا يبقى عدّ الحالات التي تساوي K تمامًا خطيًا إجمالًا.
return at_most(k) - at_most(k - 1)تعاملوا مع حالة الحافة
عندما تكون k صفرًا، سيستخدم atMost(k - 1) القيمة السالبة واحد. عالجوا هذه الحالة حتى تعيد الدالة المساعدة عددًا منطقيًا يساوي صفرًا.
مواضع التطبيق
تناسب فكرة at-most ناقص at-most عدّ المصفوفات الفرعية التي تحتوي على K من القيم المتميزة أو K من الأعداد الفردية تمامًا، أو أي خاصية رتيبة على مستوى النافذة.
تحقق سريع
تريدون عدّ المصفوفات الفرعية التي تحتوي على K من العناصر المتميزة تمامًا.
مراجعة
إن عدّ الحالات التي تساوي K تمامًا هو ببساطة atMost(K) ناقص atMost(K - 1). وتحرك كل دالة مساعدة نافذة بتعقيد O(n)، لذلك يبقى العد الكامل خطيًا. ✅
الأسئلة الشائعة
هل درس «عدّ النوافذ التي تحقق قاعدة» مجاني؟
نعم — نص درس «عدّ النوافذ التي تحقق قاعدة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «عدّ النوافذ التي تحقق قاعدة»؟
حيلة at-most-K ناقص at-most-(K-1) تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «عدّ النوافذ التي تحقق قاعدة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- مجاميع نافذة ثابتة الحجم
- نافذة متغيرة بمؤشرين
- أطول سلسلة فرعية دون تكرار
- عدّ النوافذ التي تحقق قاعدة