أقنعة البتات كمجموعات صغيرة
تمثيل المجموعات الجزئية كأعداد صحيحة
أقنعة البتات كمجموعات صغيرة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
عدد صحيح بوصفه مجموعة
يمكن لعدد صحيح واحد أن يمثّل مجموعة كاملة: فإذا كان البت i يساوي 1، فهذا يعني أن العنصر i موجود فيها. وهكذا تُخزَّن المجموعات الجزئية في قيمة واحدة صغيرة وسريعة. 🎒
المجموعتان الفارغة والكاملة
يمثّل العدد 0 المجموعة الفارغة، بينما تعني قيمة تكون فيها أدنى n بتات مفعّلة أن جميع العناصر موجودة.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsإضافة عنصر
لإضافة العنصر i إلى المجموعة، أجرِ OR مع البت الخاص به. وهذه هي بالضبط عملية تعيين بت، لكننا نقرأها هنا بوصفها اتحادًا مع عنصر واحد.
s = 0
s |= (1 << 2) # add element 2إزالة عنصر
لإزالة العنصر i، أجرِ AND مع البت المعكوس. يغادر العنصر المجموعة بينما تبقى جميع العناصر الأخرى دون تغيير. وهذا هو فرق مجموعة بعنصر واحد.
s &= ~(1 << 2) # remove element 2اختبار الانتماء
تحقق مما إذا كان العنصر i ينتمي إلى المجموعة بإجراء AND مع البت الخاص به. تعني النتيجة غير الصفرية أنه عضو في المجموعة.
if s & (1 << 2):
print('2 is in the set')الاتحاد والتقاطع
أجرِ OR لقناعين للحصول على اتحادهما، وAND للحصول على تقاطعهما. وتتحول عمليات المجموعات الكاملة إلى تعليمة آلة واحدة لكل عملية.
union = a | b
inter = a & bحجم المجموعة هو popcount
عدد العناصر في bitmask هو ببساطة عدد البتات المعيّنة فيه. استخدم bit_count للحصول على الحجم فورًا.
size = mask.bit_count()التكرار على جميع المجموعات الجزئية
بالنسبة إلى n من العناصر، تعدّد الأعداد الصحيحة من 0 إلى 2 أس n ناقص 1 كل مجموعة جزئية. وتغطيها جميعًا حلقة range بسيطة.
for mask in range(1 << n):
pass # mask is one subsetالتكرار السريع على الأقنعة الجزئية
لزيارة المجموعات الجزئية لقناع معيّن فقط، استخدم حلقة submask التقليدية. وهي تمر على كل مجموعة جزئية بترتيب تنازلي.
sub = mask
while sub:
sub = (sub - 1) & maskهنا تظهر Bitmask DP
تُستخدم الأقنعة الثنائية بوصفها حالة في مسائل DP كثيرة، مثل مسألة البائع المتجول، حيث يتتبع القناع العقد التي زرتها.
حافظ على صِغر n
مع وجود 2 أس n من المجموعات الجزئية، تظل هذه الحيلة عملية فقط عندما تكون n صغيرة، وعادةً حتى نحو 20. بعد ذلك ينفجر العدد بسرعة. ⚠️
تحقق سريع
سؤال أخير عن المجموعة بوصفها قناعًا.
مراجعة: مجموعات الأقنعة الثنائية
يمكنك تخزين مجموعة في عدد صحيح واحد، وإضافة العناصر وإزالتها باستخدام الأقنعة، والتكرار على كل مجموعة جزئية. وهذا يفتح الباب أمام Bitmask DP السريع. 🎉
تعلم Coding Interview Prep مع معلم ذكاء اصطناعي — مجانًا
اكتب وقم بتشغيل أكوادك الفعلية في المتصفح، واحصل على مساعدة فورية من معلم ذكاء اصطناعي متاح 24/7، واستمر من حيث توقفت على الويب أو في التطبيق.
- الدورات
- 90
- الدروس
- 360
الأسئلة الشائعة
هل درس «أقنعة البتات كمجموعات صغيرة» مجاني؟
نعم — نص درس «أقنعة البتات كمجموعات صغيرة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «أقنعة البتات كمجموعات صغيرة»؟
تمثيل المجموعات الجزئية كأعداد صحيحة تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «أقنعة البتات كمجموعات صغيرة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- AND وOR وXOR والإزاحات
- تعيين البت ومسحه وتبديله
- عدّ البتات وأدنى بت معيّن
- أقنعة البتات كمجموعات صغيرة