Plus One
מספר שלם לא שלילי מאוחסן כמערך של הספרות העשרוניות שלו, digits, כשהספרה המשמעותית ביותר ראשונה: 472 הוא [4, 7, 2]. הוסף 1 למספר והחזר את ספרות התוצאה באותה צורה. המספר יכול להכיל עד 100 ספרות, הרבה יותר ממה שמספר שלם בן 64 סיביות יכול להכיל.
פונקציה
- digitsinteger-array
- הספרות של המספר, מהמשמעותית ביותר תחילה
- מחזירהinteger-array
- הספרות של המספר ועוד אחת, מהספרה המשמעותית ביותר לקטנה ביותר
אילוצים
1 ≤ digits.length ≤ 1000 ≤ digits[i] ≤ 9digitsאינו מתחיל באפס, למעט המספר 0 עצמו, שהוא[0].
דוגמאות
- קלט
- digits = [4, 3, 9]
- פלט
- [4, 4, 0]
- הסבר
- המספר הוא 439, ו־439 + 1 = 440. הספרה האחרונה 9 הופכת ל־0 ומעבירה נשא אל 3, שהופך ל־4.
- קלט
- digits = [9, 9]
- פלט
- [1, 0, 0]
- הסבר
- 99 + 1 = 100. שתי הספרות 9 הופכות ל־0, והנשיאה שנותרת הופכת לספרה מובילה חדשה, כך שהתשובה ארוכה בספרה אחת מהקלט.
- קלט
- digits = [0]
- פלט
- [1]
- הסבר
- המספר 0 נכתב כך:
[0], ו-0 + 1 = 1.
+13 בדיקות נסתרות בשליחה
שאלת המשך
איך תחסירו במקום זאת אחד ממספר שהוא לפחות 1? אילו ספרות משתנות, ומתי התוצאה מאבדת את הספרה המובילה שלה, כמו ב־[1, 0, 0]?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
גם למספר יכולות להיות 100 ספרות — יותר מדי בשביל כל מספר שלם מובנה. בצעו את החיבור על הספרות, כמו בחיבור בכתב. לאן ה־1 עובר קודם?
הוספה של 1 לספרה שקטנה מ־9 אינה יוצרת נשיאה, ולכן שום דבר משמאלה לא משתנה. רק 9 הופך ל־0 ומעביר נשיאה הלאה.
עוברים מהספרה האחרונה שמאלה. הופכים כל 9 ל-0; בספרה הראשונה שקטנה מ-9, מוסיפים 1 ומחזירים. אם לא מוצאים ספרה כזו, כל הספרות היו 9: התשובה היא 1 ואחריו אפסים.
פתרון
המרת הספרות למספר, הוספת אחד והמרה בחזרה נכשלות כאן: 100 ספרות חורגות מהטווח של כל מספר שלם בן 64 סיביות, שעוצר בסביבות 1.8 × 10^19. לכן מוסיפים כפי שעושים על הנייר, מהספרה האחרונה ועם העברה. התובנה האחת שמקצרת את העבודה: הוספת 1 משנה רק את ספרות ה־9 שבסוף, שהופכות ל־0, ואת הספרה הראשונה שמשמאלן. כל ספרה אחרת נשארת כפי שהיא.
חיבור עם נשא, ספרה אחר ספרה
האינטואיציה
כתוב את המספר והוסף 1 מתחת לספרה האחרונה שלו, כמו בבית הספר. התחל עם נשא של 1, שאותו אתה מוסיף. בכל ספרה, מימין לשמאל, הסכום בעמודה הוא הספרה ועוד הנשא. הספרה האחרונה שלו, total % 10, נכנסת לתשובה, וספרת העשרות שלו, total / 10, היא הנשא לעמודה הבאה.
עם נשא של 1, הסכום בעמודה הוא לכל היותר 9 + 1 = 10, ולכן הנשא הוא תמיד 0 או 1. אם עדיין נותר נשא אחרי הספרה הראשונה, התשובה מקבלת ספרה מובילה חדשה: עבור 999 + 1 דרוש מקום רביעי עבור ה-1 של 1000.
התשובה מתקבלת מהספרה האחרונה לראשונה, כי זה הסדר שבו מחשבים אותה. אסוף אותה בסדר הזה והפוך אותה בסוף. הדבר דורש זמן O(n) ומערך חדש של עד n + 1 ספרות.
אלגוריתם
- הגדר את
carryל־1 והתחל רשימה ריקה עבור התשובה. - עבור כל ספרה, מהאחרונה לראשונה, חשב את
total = digit + carry. - הוסף את
total % 10לתשובה והגדר אתcarryל־total / 10, בעיגול כלפי מטה. - אחרי הלולאה, אם
carryהוא 1, הוסף אותו. - הפוך את התשובה והחזר אותה.
def plusOne(digits):
result = [] # the answer, last digit first
carry = 1 # the one you are adding
for i in range(len(digits) - 1, -1, -1):
total = digits[i] + carry
result.append(total % 10)
carry = total // 10
if carry > 0:
result.append(carry)
result.reverse()
return resultעצור בספרה הראשונה שמתחת ל־9
האינטואיציה
שימו לב מה קורה לנשיאה כשמוסיפים בדיוק 1. ספרה קטנה מ־9 סופגת אותה: 3 הופכת ל־4, הנשיאה הופכת ל־0, וכל ספרה שמשמאלה שומרת על הערך שלה. רק 9 מעבירה את הנשיאה הלאה, כשהיא הופכת ל־0. לכן הוספת 1 פירושה: להפוך את ספרות ה־9 שבסוף ל־0, ואז להוסיף 1 לספרה שממש לפניהן.
עברו מהספרה האחרונה שמאלה. אם הספרה היא 9, כתבו 0 והמשיכו. בכל ספרה אחרת, הגדילו אותה באחד והחזירו את המערך מיד, מכיוון ששום דבר משמאלה לא יכול להשתנות. עבור [2, 9, 0, 9] ה־9 האחרון הופך ל־0, ה־0 הופך ל־1, ועוצרים עם [2, 9, 1, 0] בלי לבדוק את שתי הספרות הראשונות.
אם הלולאה לא מוצאת אף פעם ספרה קטנה מ־9, כל הספרות היו 9 וכעת הן 0. המספר היה 10^n - 1, ולכן התוצאה היא 1 ואחריו n אפסים. זהו המקרה היחיד שדורש מערך חדש. בכל מקרה אחר משנים את הקלט במקום, ולכן המקום הנוסף הוא O(1), והלולאה רצה פעם אחת לכל 9 שבסוף ועוד צעד אחד.
אלגוריתם
- עבור על האינדקסים מהאחרון לראשון.
- אם הספרה קטנה מ־9, הגדל אותה באחד והחזר את המערך.
- אחרת, הספרה היא 9: קבע אותה ל־0 ועבור מקום אחד שמאלה.
- אם הלולאה מסתיימת, כל הספרות היו 9: החזר 1 ואחריו
nאפסים.
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1 # no carry leaves this digit, so the rest stays as it is
return digits
digits[i] = 0 # 9 + 1 = 10: write 0 and carry one to the left
# Every digit was 9: the answer is 1 followed by zeros.
return [1] + digits
מלכודות ומקרי קצה
המלכודות הן גלישת מספר שלם והמקרה שבו כל הספרות הן 9.
- המרת המערך למספר שלם ובחזרה. הוא עובר בדיקות קטנות, ואז נכשל במקרים בני 100 ספרות: מספר שלם בן 64 סיביות מכיל לכל היותר 19 או 20 ספרות, ומספר בנקודה צפה מאבד את הספרות האחרונות אפילו מוקדם יותר.
- שוכחים את הספרה הנוספת.
[9, 9, 9]חייב להפוך ל-[1, 0, 0, 0], ארבע ספרות. קוד שרק משנה את המקומות הקיימים מחזיר[0, 0, 0]. - מוסיפים 1 לספרה הראשונה במקום לאחרונה. המערך מסודר מהספרה המשמעותית ביותר לראשונה, לכן ספרת היחידות נמצאת בסוף.
- שוכחים להחזיר אחרי שספרה קטנה מ-9 סופגת את הנשיאה. בגרסה שיוצאת מוקדם, הלולאה ממשיכה ומשנה ספרות שאמורות להישאר כפי שהן. ב-
[1, 9, 3]רק ה-3 יכולה להשתנות; התשובה היא[1, 9, 4]. - מתבלבלים בסדר האינדקסים ב-Lua וב-R, שבהן מערכים מתחילים ב-1: הספרה האחרונה נמצאת באינדקס
n, ו-1 מוביל חדש נכנס לפני אינדקס 1.
שאלות נפוצות4
מהי סיבוכיות הזמן של Plus One?
שתי הגישות רצות בזמן O(n) עבור n ספרות, כי במקרה הגרוע ביותר, כשכולן 9, נוגעים בכל הספרות. הגרסה עם היציאה המוקדמת נעצרת אחרי ספרות ה־9 שבסוף, ולכן עבור מספר שמסתיים בספרה קטנה מ־9 היא מבצעת צעד אחד. היא משתמשת במקום נוסף של O(1), למעט כשהתשובה דורשת ספרה מובילה חדשה.
למה לא להמיר את הספרות למספר שלם?
מכיוון שהמספר יכול להכיל 100 ספרות, ואילו מספר שלם בן 64 סיביות מוגבל לכ־1.8 × 10^19, שהם 20 ספרות. ל־Python ול־Ruby יש מספרים שלמים ללא הגבלה, ולכן ההמרה עובדת בהן, אבל היא מסתירה את מטרת התרגיל ואינה מתאימה לשפות אחרות. עבודה ספרה אחר ספרה לעולם אינה גורמת לגלישה.
מתי יש לתוצאה יותר ספרות מאשר לקלט?
רק כאשר כל ספרה היא 9. אז המספר הוא 10^n - 1, והוספת אחת נותנת 10^n: 1 ואחריו n אפסים. אם ספרה כלשהי קטנה מ־9, היא סופגת את הנשיאה, ולכן האורך נשאר זהה.
איך מחברים שני מספרים המאוחסנים כמערכי ספרות?
השתמשו בשיטת העמודות מהגישה הראשונה, עם שני אינדקסים — אחד בסוף כל מערך. בכל עמודה מחברים את שתי הספרות, ומתייחסים לספרה חסרה כאל 0, יחד עם הנשיאה. המשיכו עד ששני המערכים נוצלו והנשיאה היא 0, ואז הפכו את סדר הספרות שנאספו.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def plusOne(digits):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
digits = [4, 3, 9]
צפוי
[4, 4, 0]