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
- الشرح
- تشكّل قيم
1sثلاثة تتابعات: الفهارس من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.
+14 اختبارات مخفية عند الإرسال
سؤال إضافي
ماذا لو كان بإمكانك قلب ما يصل إلى k من الأصفار إلى آحاد؟ ما طول أطول سلسلة من الآحاد التي يمكنك الحصول عليها، وهل لا يزال بإمكانك إيجادها في مرور واحد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تنتهي سلسلة من الأرقام 1 بمجرد ظهور
0. ما الذي تحتاج إلى تذكّره بشأن القيم التي مررت بها بالفعل؟لا يهم سوى طول التتابع الذي ينتهي عند الفهرس الحالي. تجعل القيمة 1 التتابع أطول بمقدار واحد، بينما تعيده القيمة 0 إلى الصفر.
مرّ على المصفوفة مرة واحدة باستخدام عددين: طول التتابع الحالي وأفضل طول حتى الآن. بعد كل 1، زد طول التتابع الحالي وقارنه بالأفضل؛ وبعد كل 0، أعد ضبط طول التتابع الحالي.
الحل
تنتهي سلسلة التتابع لحظة ظهور 0، لذا فإن الشيء الوحيد الذي تحتاج إلى معرفته عند أي فهرس هو طول سلسلة التتابع التي تنتهي عنده. إن العد من البداية عند كل فهرس يكرر العمل نفسه مرارًا وتكرارًا. عدّاد واحد يزداد عند ظهور 1 ويُعاد ضبطه عند ظهور 0 يجيب عن السؤال في مرور واحد.
عُدّ تصاعديًا بدءًا من كل فهرس
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
يبدأ كل تتابع من موضع ما. لذا جرّب كل فهرس كبداية، وتقدّم إلى الأمام ما دمت ترى قيمًا تساوي 1؛ فعدد الخطوات هو طول التتابع الذي يبدأ من ذلك الموضع. أكبر عدد بين جميع البدايات هو الإجابة. في [1, 1, 0, 1, 1, 1, 0, 1]، يتقدّم الفهرس 3 عبر ثلاث قيم تساوي 1 قبل أن يصل إلى 0 عند الفهرس 6، فيكون الناتج 3.
الإجابة صحيحة لأن أطول تتابع يبدأ عند أحد الفهارس التي تجرّبها، ومن فهرسه الأول يقيس التقدّم طوله بدقة.
تكمن الكلفة في التداخل. في مصفوفة تحتوي على n من القيم التي تساوي 1، يتقدّم الفهرس 0 بمقدار n خطوات، والفهرس التالي بمقدار n-1، وهكذا، ليصل المجموع إلى نحو n² / 2 خطوة. عندما تكون n = 2 × 10^4، فهذا يعني 2 × 10^8 خطوة، وهو عدد كبير جدًا بالنسبة إلى الحد الزمني في اللغات الأبطأ.
الخوارزمية
- عيّن
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 تلك السلسلة، لذا تزداد قيمة current بمقدار واحد. وينهيها العدد 0، لذا تعود قيمة current إلى 0. بعد كل 1، قارن current بـ best.
في [1, 1, 0, 1, 1, 1, 0, 1]، تأخذ current القيم 1، 2، 0، 1، 2، 3، 0، 1، وأكبرها هو 3. تُقاس كل سلسلة عند فهرسها الأخير، حيث تساوي current طولها الكامل، لذا فإن أفضل قيمة تم الوصول إليها هي طول أطول سلسلة.
تُقرأ كل قيمة مرة واحدة، وهذا يستغرق وقتًا قدره O(n)، ويكفيك عددان صحيحان من الذاكرة.
الخوارزمية
- عيّن
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من تسلسلات منفصلة ويُرجع4للمصفوفة[1, 1, 0, 1, 1]. - بدء
bestبقيمة1أو بقيمةnums[0]. يجب أن تُرجع المصفوفة التي تحتوي على أصفار فقط0. - في Lua وR، يبدأ فهرس المصفوفة من
1، لذا يتحقق المرور الأمامي منstart + length ≤ nبدلًا من< n.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة أطول سلسلة من الواحدات المتتالية؟
يعمل الحل ذو المرور الواحد في زمن O(n)، لأنه يقرأ كل قيمة مرة واحدة بالضبط. ويستخدم مساحة إضافية O(1): عدّادًا للمجموعة الحالية وآخر للأفضل. إعادة بدء العدّ عند كل فهرس تستغرق زمنًا قدره O(n²) على مصفوفة تحتوي على قيم 1 فقط.
لماذا يُعاد ضبط العداد إلى 0 بدلًا من 1؟
يحتفظ العداد بطول سلسلة الأرقام التي تنتهي عند الفهرس الحالي. عندما تكون القيمة الحالية 0، لا تنتهي هناك أي سلسلة من الأرقام 1، لذا يكون طولها 0. ثم يرفعها الرقم 1 التالي إلى 1، وهو الطول الصحيح لسلسلة جديدة.
هل هذه مسألة نافذة منزلقة؟
يمكنك تصوّرها كنافذة واحدة: تحتوي النافذة على المقطع الحالي، وتتحرك الحافة اليمنى عند كل قيمة، بينما يجعل 0 الحافة اليسرى تتجاوزه. هنا لا تحتاج النافذة إلى أن تنكمش خطوة بخطوة، لذا يحلّ عدّاد واحد محل الحافتين. تظهر فائدة طريقة النافذة في النسخة الأصعب، حيث يمكنك قلب ما يصل إلى k من الأصفار إلى آحاد.
كيف تحسب عدد وحدات 1 المتتالية إذا كان بإمكانك قلب 0 واحد؟
احتفظ بعدّادين: طول التتابع المنتهي هنا دون قلب، وطوله بعد استخدام قلب واحد. عند ظهور 1، يزداد كلاهما بمقدار واحد. عند ظهور 0، يصبح عدّاد القلب مساويًا للعدّاد العادي زائد واحد، ويُصفّر العدّاد العادي. الإجابة هي أكبر قيمة لعدّاد القلب تراها، وكل ذلك في مرور واحد.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def findMaxConsecutiveOnes(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [1, 1, 0, 1, 1, 1, 0, 1]
المتوقع
3