Max Consecutive Ones
لديك مصفوفة nums تحتوي كل قيمة فيها على 0 أو 1. السلسلة المتتالية هي مجموعة من قيم 1 متجاورة لا يفصل بينها أي 0. أعد طول أطول سلسلة متتالية، أو 0 إذا لم تحتوِ المصفوفة على أي 1.
الدالة
- numsinteger-array
- مصفوفة من الأصفار والآحاد
- تُرجعinteger
- طول أطول سلسلة متتالية من الرقم 1
القيود
1 ≤ nums.length ≤ 2 × 104- كل
nums[i]إما0أو1.
أمثلة
- المدخلات
- nums = [1, 1, 0, 1, 1, 1, 0, 1]
- المخرجات
- 3
- الشرح
- تشكل قيم
1ثلاث سلاسل متتالية: من الفهرس0إلى1(بطول 2)، ومن3إلى5(بطول 3)، والفهرس7وحده (بطول 1). أطولها طوله3.
- المدخلات
- nums = [0, 1, 0, 1, 1]
- المخرجات
- 2
- الشرح
- العدد 1 المفرد عند الفهرس
1يخسر أمام الزوج عند الفهرسين3و4، لذا الإجابة هي2.
- المدخلات
- nums = [0, 0, 0]
- المخرجات
- 0
- الشرح
- لا يوجد الرقم 1 في أي مكان، لذا لا يوجد تسلسل متصل والإجابة هي
0.
سؤال إضافي
ماذا لو كان بإمكانك قلب ما يصل إلى k من الأصفار إلى آحاد؟ ما الطول الذي يمكن أن يبلغه أطول تتابع، وهل لا يزال بإمكانك إيجاده في مرور واحد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ينتهي تتابع الواحدات لحظة ظهور
0. ما الذي تحتاج إلى تذكّره بشأن القيم التي مررت بها بالفعل؟المهم فقط هو طول السلسلة المتواصلة التي تنتهي عند الفهرس الحالي. تجعلها القيمة 1 أطول بمقدار واحد، بينما تعيدها القيمة 0 إلى الصفر.
امشِ على المصفوفة مرة واحدة باستخدام عددين: طول التسلسل الحالي وأفضل طول حتى الآن. بعد كل 1، زِد طول التسلسل الحالي وقارنه بالأفضل؛ وبعد كل 0، أعد ضبط طول التسلسل الحالي.
الحل
ينتهي التسلسل فور ظهور 0، لذا لا تحتاج عند كل فهرس إلا إلى طول التسلسل المنتهي عنده. يكفي عدّاد واحد يزداد عند ظهور 1 ويُصفّر عند ظهور 0 للعثور على أطول تسلسل في مرور واحد.
عُدّ تصاعديًا بدءًا من كل فهرس
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
جرّب كل فهرس كنقطة بداية، وتقدّم للأمام ما دمت ترى قيمًا تساوي 1؛ عدد الخطوات هو طول السلسلة التي تبدأ عند ذلك الفهرس. تبدأ أطول سلسلة عند أحد هذه الفهارس، لذا فإن أكبر عدد هو الإجابة.
تتداخل عمليات التقدّم. في مصفوفة تتكوّن من n من الواحدات، تستغرق نحو n² / 2 خطوة، أي 2 × 10^8 عندما تكون n = 2 × 10^4.
الخوارزمية
- عيّن
best = 0. - لكل فهرس
start، عيّنlength = 0. - ما دام
start + lengthضمن المصفوفة وnums[start + length]يساوي1، أضف 1 إلىlength. - احتفظ بالقيمة الأكبر من
bestوlength. - أعِد
best.
def findMaxConsecutiveOnes(nums):
n = len(nums)
best = 0
for start in range(n):
length = 0
while start + length < n and nums[start + length] == 1:
length += 1
best = max(best, length)
return bestتمرير واحد مع عدّاد جارٍ
الفكرة
احتفِظ بـ current، وهو طول سلسلة الأرقام 1 التي تنتهي عند الفهرس الذي وصلت إليه. يضيف الرقم 1 واحدًا إلى طول السلسلة؛ أما الرقم 0 فينهيها، لذا تنخفض قيمة current إلى 0. يُقاس طول كل سلسلة عند فهرسها الأخير، حيث تساوي قيمة current طولها الكامل، لذا فإن أكبر قيمة تصل إليها current هي الإجابة.
في [1, 1, 0, 1, 1, 1, 0, 1]، تأخذ current القيم 1 و2 و0 و1 و2 و3 و0 و1، وأكبرها 3.
الخوارزمية
- عيّن
best = 0وcurrent = 0. - لكل قيمة في
nums: إذا كانت1، فأضف 1 إلىcurrentواحتفظ بالقيمة الأكبر بينbestوcurrent. - إذا كانت
0، فعيّنcurrent = 0. - أعِد
best.
def findMaxConsecutiveOnes(nums):
best = 0
current = 0
for x in nums:
if x == 1:
current += 1
best = max(best, current)
else:
# A 0 breaks the run.
current = 0
return best
أخطاء شائعة وحالات حدّية
- تحديث
bestفقط عند الوصول إلى0. لا يُسجَّل أي تسلسل يصل إلى النهاية، مثل[0, 1, 1]. حدّث القيمة بعد كل1، أو أجرِ مقارنة إضافية بعد انتهاء الحلقة. - عدم إعادة تعيين
currentعند الوصول إلى0. تتراكم التسلسلات المنفصلة، لذا تُرجع[1, 1, 0, 1, 1]القيمة4. - بدء
bestبالقيمة1أو بالقيمةnums[0]. يجب أن تُرجع[0, 0, 0]القيمة0. - في Lua وR، حيث تبدأ المصفوفات من 1، استخدام
< nبدلًا من≤ nلتحديد حدّ المرور إلى الأمام. لن تُقرأ القيمة الأخيرة أبدًا، لذا تُرجع[0, 1]القيمة0.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة أطول سلسلة من الواحدات المتتالية؟
يعمل الحل بتمريرة واحدة في زمن O(n)، لأنه يقرأ كل قيمة مرة واحدة، ويستخدم مساحة إضافية O(1): عدّادًا واحدًا للتتابع الحالي وآخر للأفضل. تؤدي إعادة بدء العد عند كل فهرس إلى زمن O(n²) عند استخدام مصفوفة تتكون كلها من 1s.
لماذا يُعاد ضبط العداد إلى 0 بدلًا من 1؟
يحمل العداد طول التسلسل الذي ينتهي عند الفهرس الحالي. عندما تكون القيمة هناك 0، لا ينتهي عنده أي تسلسل من الرقم 1، لذا يكون الطول 0. يرفعه الرقم 1 التالي إلى 1، وهو طول التسلسل الجديد.
هل تُعدّ مسألة أطول سلسلة متتالية من الواحدات مسألة نافذة منزلقة؟
يمكنك رؤيتها كنافذة واحدة: تحتوي النافذة على المقطع الحالي، وتتحرك حافتها اليمنى مع كل قيمة، بينما ينقل 0 الحافة اليسرى إلى ما بعده. لا تتقلص النافذة خطوةً بخطوة، لذا يحلّ عدّاد واحد محل الحافتين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def findMaxConsecutiveOnes(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [1, 1, 0, 1, 1, 1, 0, 1]
الإخراج المتوقع
3