Counting Bits

Q: ما هو التعقيد الزمني لعدّ البتات؟

يعمل الحل الأفضل في زمن O(n): يأتي كل إدخال من الإدخالات n+1 من إدخال سابق واحد مع عملية جمع واحدة. يستغرق عدّ بتات كل عدد على حدة زمنًا قدره O(n log n). يستخدم كلا الحلين ذاكرة O(1) إضافية تتجاوز مصفوفة الإخراج.

Q: هل توجد علاقة عودية أخرى بزمن O(n) لعدّ البتات؟

نعم. يمسح i & (i-1) أقل بتّ يساوي 1 في i ، لذا فإن bits[i] = bits[i & (i-1)] + 1 لكل i يساوي 1 أو أكثر. بالنسبة إلى 12 ( 1100 )، فإن 12 & 11 يساوي 8 ( 1000 )، الذي يحتوي على 1 واحد، لذا يحتوي 12 على اثنين.

Q: هل يمكنني استخدام دالة popcount مدمجة؟

إن استدعاء واحدة لكل رقم، مثل Integer.bitCount في Java أو __builtin_popcount في C وC++، يعطي إجابة صحيحة. عادةً ما يطلب القائمون بالمقابلات حلًا من دونها، لأن الهدف من المسألة هو إعادة استخدام الإجابات التي حسبتها مسبقًا.

سهلمعالجة البتات البرمجة الديناميكية

+10

معطى عدد صحيح غير سالب n، أعد مصفوفة تحتوي على n+1 عنصرًا، بحيث يكون العنصر i هو عدد الـ1ات في التمثيل الثنائي لـi، لكل i من 0 إلى n.

الدالة

countBits(n: integer) → integer-array

ninteger: العدد الأخير للعدّ، 0 أو أكثر
تُرجعinteger-array: مصفوفة من n+1 عددًا، حيث إن العنصر i هو عدد البتات 1 في i

القيود

0 ≤ n ≤ 2 × 10⁴

أمثلة

المدخلات: n = 2
المخرجات: [0, 1, 1]
الشرح: في النظام الثنائي، 0 هو 0، و1 هو 1، و2 هو 10: لا توجد أيّ 1، ثم واحد، ثم واحد.

المدخلات: n = 5
المخرجات: [0, 1, 1, 2, 1, 2]
الشرح: 3 هو 11 و5 هو 101، ولكل منهما اثنان من الرقم 1؛ أما 4 فهو 100، وفيه واحد. ومع 0 و1 و2 من المثال الأول، تكون الأعداد 0 و1 و1 و2 و1 و2.

سؤال إضافي

هل يمكنك ملء المصفوفة بأكملها في زمن O(n)، دون استخدام دالة مضمّنة تحسب البتات، ودون حساب كل عدد من البداية؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

إن عدَّ كل عدد من البداية يكرر العمل: العدد 13 هو 1101، أي بتات العدد 6 (110) مع إضافة خانة أخرى في النهاية. املأ الإجابات بترتيب تصاعدي، فكل مدخلة تعيد استخدام مدخلة أصغر مع إضافة واحدة.

احسب بتات كل عدد

الفكرة

احسب كل بتات الواحد في كل عدد مباشرةً: أضف x & 1 إلى عدّاد، وأزِح x إلى اليمين بمقدار بت واحد، وتوقّف عند 0. بالنسبة إلى 13 (1101)، تكون البتات 1، 0، 1، 1، لذا يكون العدد 3.

يحتوي عدد لا يتجاوز n على نحو log2 n من الخانات الثنائية، لذا يكون التنفيذ O(n log n): نحو 20,000 × 15 = 300,000 خطوة عندما تكون n = 2 × 10^4.

الخوارزمية

ابدأ قائمة نتائج فارغة.
لكل i من 0 إلى n، عيّن count إلى 0 وx إلى i.
ما دام x أكبر من 0، أضف x & 1 إلى count وأزِح x إلى اليمين بمقدار واحد.
ألحِق count بالنتيجة.
أعِد النتيجة.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

اضرب نصف العدد في نفسه

الفكرة

إزاحة i إلى اليمين بمقدار واحد تحذف آخر رقم ثنائي منه، وi & 1 هو ذلك الرقم. لذا يحتوي i على أرقام الواحد في i >> 1 بالإضافة إلى رقمه الأخير: bits[i] = bits[i >> 1] + (i & 1).

لكل i قيمته 1 أو أكثر، تكون i >> 1 أصغر من i، لذا فإن ملء المصفوفة من اليسار إلى اليمين، بدءًا من bits[0] = 0، يعني أن القيمة التي تقرؤها تكون جاهزة دائمًا. عندما تكون قيمة n هي 5: bits[3] = bits[1] + 1 = 2، وbits[4] = bits[2] + 0 = 1، وbits[5] = bits[2] + 1 = 2.

كل عنصر يحتاج إلى إزاحة واحدة وعملية AND واحدة وعملية جمع واحدة: زمن O(n) ولا حاجة إلى ذاكرة إضافية تتجاوز مساحة الإخراج.

الخوارزمية

أنشئ مصفوفة bits تحتوي على n+1 من الأصفار. تبقى bits[0] مساوية لـ 0.
لكل i من 1 إلى n، عيّن bits[i] إلى bits[i >> 1] + (i & 1).
أعِد bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

أخطاء شائعة وحالات حدّية

إرجاع n مُدخلات بدلًا من n+1. عندما تكون n = 0، تكون الإجابة [0].
أسبقية المعاملات. في Python وC وJava وJavaScript، تكون أسبقية + أعلى من أسبقية &، لذا تعني bits[i >> 1] + i & 1 (bits[i >> 1] + i) & 1. أبقِ الأقواس حول (i & 1).
البحث عن bits[i-1] بدلًا من bits[i >> 1]. لا توجد قاعدة بسيطة مشتركة بين الأعداد المتجاورة: العدد 7 هو 111 وفيه ثلاثة أرقام 1، والعدد 8 هو 1000 وفيه رقم 1 واحد.
في Lua وR، تبدأ المصفوفات من 1، لذا يكون عدد i عند الفهرس i+1، ويكون البحث عن i >> 1 عند floor(i/2) + 1. لا يدعم Lua 5.1 معامل الإزاحة، لذا اقسم على 2 باستخدام math.floor(i / 2).

أسئلة شائعة3

ما هو التعقيد الزمني لعدّ البتات؟

يعمل الحل الأفضل في زمن O(n): يأتي كل إدخال من الإدخالات n+1 من إدخال سابق واحد مع عملية جمع واحدة. يستغرق عدّ بتات كل عدد على حدة زمنًا قدره O(n log n). يستخدم كلا الحلين ذاكرة O(1) إضافية تتجاوز مصفوفة الإخراج.

هل توجد علاقة عودية أخرى بزمن O(n) لعدّ البتات؟

نعم. يمسح i & (i-1) أقل بتّ يساوي 1 في i، لذا فإن bits[i] = bits[i & (i-1)] + 1 لكل i يساوي 1 أو أكثر. بالنسبة إلى 12 (1100)، فإن 12 & 11 يساوي 8 (1000)، الذي يحتوي على 1 واحد، لذا يحتوي 12 على اثنين.

هل يمكنني استخدام دالة popcount مدمجة؟

إن استدعاء واحدة لكل رقم، مثل Integer.bitCount في Java أو __builtin_popcount في C وC++، يعطي إجابة صحيحة. عادةً ما يطلب القائمون بالمقابلات حلًا من دونها، لأن الهدف من المسألة هو إعادة استخدام الإجابات التي حسبتها مسبقًا.

def countBits(n):
    # اكتب الكود هنا

اختبار #1

اختبار #2

وسيط

n = 2

الإخراج المتوقع

[0, 1, 1]