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, והאם עדיין אפשר למצוא אותו במעבר אחד?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
רצף של 1s מסתיים ברגע שמופיע
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, אורך רצף ה־1s שמסתיים באינדקס הנוכחי. 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-ים חייב להחזיר0. - ב-Lua וב-R המערך מתחיל באינדקס
1, לכן ההליכה קדימה בודקתstart + length ≤ nבמקום< n.
שאלות נפוצות4
מהי סיבוכיות הזמן של Max Consecutive Ones?
פתרון במעבר אחד פועל בזמן O(n), כי הוא קורא כל ערך בדיוק פעם אחת. הוא משתמש בזיכרון נוסף של O(1): מונה אחד לרצף הנוכחי ואחד לרצף הארוך ביותר. איפוס המונה בכל אינדקס דורש זמן O(n²) במערך שכולו 1.
למה המונה מתאפס ל־0 במקום ל־1?
המונה מכיל את אורך הרצף שמסתיים באינדקס הנוכחי. כשהערך הנוכחי הוא 0, לא מסתיים שם רצף של 1s, ולכן אורכו הוא 0. ה־1 הבא מעלה אותו ל־1, שהוא האורך הנכון של רצף חדש.
האם זו בעיית חלון הזזה?
אפשר לראות את זה כחלון אחד: החלון מכיל את הרצף הנוכחי, הקצה הימני מתקדם בכל ערך, ו־0 מזיז את הקצה השמאלי מעבר אליו. כאן החלון אף פעם לא צריך להצטמצם צעד אחר צעד, ולכן מונה יחיד מחליף את שני הקצוות. התצוגה כחלון מועילה בגרסה הקשה יותר, שבה אפשר להפוך עד k אפסים לאחדות.
איך סופרים רצפים של 1 אם אפשר להפוך 0 אחד?
נהלו שני מונים: אורך הרצף שמסתיים כאן ללא היפוך, ואורך הרצף לאחר שכבר השתמשנו בהיפוך אחד. כשמופיע 1, שניהם גדלים באחד. כשמופיע 0, המונה של הרצף לאחר היפוך מקבל את ערך המונה הרגיל ועוד אחד, והמונה הרגיל מתאפס ל-0. התשובה היא הערך הגדול ביותר של מונה הרצף לאחר היפוך שנתקלתם בו, והכול במעבר אחד.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def findMaxConsecutiveOnes(nums):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [1, 1, 0, 1, 1, 1, 0, 1]
צפוי
3