عدّ النوافذ التي تحقق قاعدة
حيلة at-most-K ناقص at-most-(K-1)
عدّ النوافذ التي تحقق قاعدة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 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)، لذلك يبقى العد الكامل خطيًا. ✅
تعلم Python مع معلم ذكاء اصطناعي — مجانًا
اكتب وقم بتشغيل أكوادك الفعلية في المتصفح، واحصل على مساعدة فورية من معلم ذكاء اصطناعي متاح 24/7، واستمر من حيث توقفت على الويب أو في التطبيق.
- الدورات
- 30
- الدروس
- 120
الأسئلة الشائعة
هل درس «عدّ النوافذ التي تحقق قاعدة» مجاني؟
نعم — نص درس «عدّ النوافذ التي تحقق قاعدة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «عدّ النوافذ التي تحقق قاعدة»؟
حيلة at-most-K ناقص at-most-(K-1) تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «عدّ النوافذ التي تحقق قاعدة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- مجاميع نافذة ثابتة الحجم
- نافذة متغيرة بمؤشرين
- أطول سلسلة فرعية دون تكرار
- عدّ النوافذ التي تحقق قاعدة