Plus One

Q: מהי סיבוכיות הזמן של Plus One?

שתי הגישות פועלות בזמן O(n) עבור n ספרות, מכיוון שמקרה שכל הספרות בו הן 9 נוגע בכל ספרה. הגרסה עם היציאה המוקדמת נעצרת אחרי רצף הספרות 9 שבסוף ומשתמשת במקום נוסף של O(1) , למעט כשהתשובה דורשת ספרה מובילה חדשה.

קלמתמטיקה וסימולציה

+10

מספר שלם שאינו שלילי מאוחסן כמערך של הספרות העשרוניות שלו, digits, כשהספרה המשמעותית ביותר ראשונה: 472 הוא [4, 7, 2]. הוסף אחד למספר והחזר את ספרות התוצאה באותה צורה. המספר יכול להכיל עד 100 ספרות, הרבה יותר ממה שמספר שלם בן 64 סיביות יכול להכיל.

פונקציה

plusOne(digits: integer-array) → integer-array

digitsinteger-array: הספרות של המספר, מהמשמעותית ביותר לפחות משמעותית
מחזירהinteger-array: הספרות של המספר ועוד אחת, מהמשמעותית ביותר לפחות משמעותית

אילוצים

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits לא מתחיל באפס, למעט המספר 0 עצמו, שהוא [0].

דוגמאות

קלט: digits = [4, 3, 9]
פלט: [4, 4, 0]
הסבר: המספר הוא 439, ו־439 + 1 = 440. הספרה האחרונה 9 הופכת ל־0 ומעבירה נשא ל־3, שהופכת ל־4.

קלט: digits = [0]
פלט: [1]
הסבר: המספר 0 נכתב כך: [0], ו־0 + 1 = 1.

שאלת המשך

איך תחסירו במקום זאת אחד, עבור מספר שגדול או שווה ל־1? מתי התוצאה מאבדת את הספרה המובילה שלה, כמו ב־[1, 0, 0]?

פתרון

מספר בן 100 ספרות חורג מהטווח של כל מספר שלם בן 64 סיביות, שהגבול שלו הוא בערך 1.8 × 10^19, ולכן אי אפשר להמיר ולחבר. חברו כמו שעושים על נייר, מהספרה האחרונה עם העברה. הוספת 1 משנה רק את ספרות ה־9 שבסוף, שהופכות ל־0, ואת הספרה שמשמאלן.

חיבור עם העברה, ספרה אחר ספרה

האינטואיציה

התחל עם נשא של 1, המספר שאתה מוסיף. בכל ספרה, מימין לשמאל, סכום העמודה הוא הספרה ועוד הנשא: total % 10 נכנס לתשובה, ו־total / 10 הוא הנשא הבא. הסכום הוא לכל היותר 9 + 1 = 10, ולכן הנשא נשאר 0 או 1. נשא שנשאר אחרי הספרה הראשונה הופך לספרה מובילה חדשה, כמו ב־999 + 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

האינטואיציה

ספרה שקטנה מ־9 סופגת נשא של 1: היא גדלה באחת וכל ספרה שמשמאלה שומרת על ערכה. רק 9 מעבירה את הנשא הלאה, כשהיא הופכת ל־0. לכן אפשר לעצור בספרה הראשונה שקטנה מ־9 ולהחזיר את מערך הקלט, לאחר שינויו במקום. עבור [2, 9, 0, 9] ה־9 האחרון הופך ל־0, ה־0 הופך ל־1, ומחזירים את [2, 9, 1, 0] בלי לקרוא את שתי הספרות הראשונות.

אם אין ספרה שקטנה מ־9, המספר היה 10^n - 1 והתשובה היא 1 ואחריו n אפסים. זה המקרה היחיד שדורש מערך חדש, ולכן אחרת המקום הנוסף הוא O(1).

אלגוריתם

עבור על האינדקסים מהאחרון לראשון.
אם הספרה קטנה מ־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

מלכודות ומקרי קצה

המרת המערך למספר שלם ואז בחזרה. מספר שלם בן 64 סיביות יכול להכיל לכל היותר 19 או 20 ספרות, לכן 100 ספרות יגרמו לגלישה, ומספר בנקודה צפה מאבד את הספרות האחרונות אפילו מוקדם יותר.
שוכחים את הספרה הנוספת. [9, 9, 9] חייב להפוך ל־[1, 0, 0, 0]; קוד שרק כותב מחדש את המקומות הקיימים מחזיר [0, 0, 0].
מוסיפים 1 לספרה הראשונה. המערך מסודר מהספרה המשמעותית ביותר לראשונה, לכן ספרת היחידות היא האיבר האחרון.
לא מחזירים ערך אחרי שספרה קטנה מ־9 סופגת את הנשא. הלולאה משנה אז ספרות שצריכות להישאר ללא שינוי: [1, 9, 3] חייב להפוך ל־[1, 9, 4].
ב־Lua וב־R, מערכים מתחילים באינדקס 1, לכן הספרה האחרונה נמצאת באינדקס n, ולא n - 1.

שאלות נפוצות3

מהי סיבוכיות הזמן של Plus One?

שתי הגישות פועלות בזמן O(n) עבור n ספרות, מכיוון שמקרה שכל הספרות בו הן 9 נוגע בכל ספרה. הגרסה עם היציאה המוקדמת נעצרת אחרי רצף הספרות 9 שבסוף ומשתמשת במקום נוסף של O(1), למעט כשהתשובה דורשת ספרה מובילה חדשה.

למה לא להמיר את הספרות למספר שלם?

המספר יכול להכיל 100 ספרות, ומספר שלם בן 64 סיביות נעצר בערך ב־1.8 × 10^19, כלומר 20 ספרות. ל־Python ול־Ruby יש מספרים שלמים ללא הגבלה, ולכן ההמרה עובדת בהן, אבל הקוד לא מתאים לשפות אחרות. עבודה ספרה אחר ספרה לעולם אינה גורמת לגלישה.

איך מחברים שני מספרים המאוחסנים כמערכי ספרות?

השתמש בשיטת העמודות עם אינדקס אחד בסוף כל מערך. בכל עמודה מחברים את שתי הספרות, מתייחסים לספרה חסרה כאל 0, ומוסיפים את הנשיאה. עצור כשנגמרו שני המערכים והנשיאה היא 0, ואז הפוך את סדר הספרות שנאספו.

def plusOne(digits):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

digits = [4, 3, 9]

הפלט הצפוי

[4, 4, 0]