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