Reverse the Digits

Q: איך הופכים את סדר הספרות של מספר בלי להמיר אותו למחרוזת?

חזור על שני שלבים עד שהמספר הוא 0 : קח את הספרה האחרונה באמצעות n % 10 והוסף אותה לתוצאה באמצעות result = result * 10 + digit , ואז הסר אותה באמצעות n = n / 10 בעזרת חילוק שלמים. עבור 1234 התוצאה גדלה כך: 4, 43, 432 ו-4321.

Q: מה קורה לאפסים שבסוף כשמהפכים מספר?

הם יהפכו לאפסים מובילים, שאין במספר, ולכן הם נעלמים. היפוך 120 נותן 21 , והיפוך 100000000 נותן 1 . הלולאה האריתמטית מסירה אותם בעצמה, כי הוספת 0 לתוצאה ריקה משאירה אותה על 0 .

Q: מהי סיבוכיות הזמן של היפוך מספר שלם?

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

Q: האם היפוך של מספר שלם עלול לגרום לגלישת מספר שלם?

כן, כאשר הקלט יכול להיות כל מספר שלם בן 32 ביט. 1000000009 נכנס, אבל ההיפוך שלו 9000000001 לא. כאן n קטן מ־ 10^9 , לכן להיפוך יש לכל היותר 9 ספרות והוא תמיד נכנס. בקלטים גדולים יותר, בדקו result > (INT_MAX - digit) / 10 לפני כל כפל.

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

+10

ניתן לך מספר שלם לא שלילי n. החזר את המספר שמתקבל מכתיבת הספרות העשרוניות שלו בסדר הפוך. אפסים שמגיעים לתחילת המספר מושמטים, כך ש־120 הופך ל־21.

פונקציה

reverseDigits(n: integer) → integer

ninteger: המספר השלם הלא-שלילי שיש להפוך
מחזירהinteger: הספרות של n בסדר הפוך, כמספר

אילוצים

0 ≤ n < 10⁹
גם המספר ההפוך נכנס למספר שלם עם סימן בן 32 סיביות.

דוגמאות

קלט: n = 1234
פלט: 4321
הסבר: הספרות של 1234 הן 1, 2, 3 ו-4. בקריאה מהסוף הן 4, 3, 2 ו-1, כלומר 4321.

קלט: n = 120
פלט: 21
הסבר: בקריאה מהסוף להתחלה, 120 נותן את הספרות 0, 2 ו-1. אפס מוביל אינו נחשב כחלק ממספר, ולכן התשובה היא 21.

קלט: n = 0
פלט: 0
הסבר: ל־0 יש ספרה אחת, והיפוך שלו נותן שוב את 0.

+13 בדיקות נסתרות בשליחה

שאלת המשך

אם n יכול להיות כל מספר שלם בן 32 סיביות, ייתכן שההיפוך שלו לא יתאים. איך תזהה זאת לפני שהכפל יגרום לגלישה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

היפוך הטקסט העשרוני נעשה בשורה אחת ברוב השפות, וזוהי תשובה ראשונה טובה. מראיינים בדרך כלל שואלים בהמשך איך להגיע לאותה תוצאה בלי מחרוזות. הגרסה החשבונית מבוססת על שתי פעולות: n % 10 קוראת את הספרה האחרונה, ו־n / 10 (חלוקה במספרים שלמים) מסירה אותה.

הפוך את הטקסט העשרוני

האינטואיציה

הספרות של מספר הן בדיוק התווים בייצוג העשרוני שלו כטקסט. הפכו את n לטקסט, הפכו את סדר התווים וקראו את הטקסט בחזרה כמספר. 1234 הופך ל־"1234", ואז ל־"4321", ואז ל־4321.

האפסים המובילים מסתדרים מעצמם. הפיכת 120 נותנת את הטקסט "021", וניתוחו כמספר מתעלם מהאפס שבהתחלה ומחזיר 21.

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

אלגוריתם

המר את n לטקסט עשרוני.
הפוך את התווים.
נתח את הטקסט ההפוך כמספר שלם והחזר אותו.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

הוצאת ספרות והכנסתן באמצעות פעולות חשבון

האינטואיציה

הסר את הספרות מסופו של n אחת בכל פעם, והוסף כל אחת מהן לסופו של מספר חדש. n % 10 היא הספרה האחרונה של n, ו־n / 10 בחלוקה שלמה מסיר אותה. כדי להוסיף ספרה d לסופו של result, הזז את מה שיש בו מקום אחד שמאלה והצב את d במקום האחדות: result * 10 + d.

עבור 1234, הערך של result משתנה ל־4, 43, 432, 4321, בעוד שהערך של n משתנה ל־123, 12, 1, 0. הלולאה נעצרת כש־n מגיע ל־0, ולכן היא רצה פעם אחת לכל ספרה.

אפסים מובילים לעולם אינם מופיעים. עבור 120, הספרה הראשונה שנלקחת היא 0, ו־0 * 10 + 0 עדיין שווה ל־0, כך שלא נשאר לה זכר. עבור n = 0, הלולאה אינה רצה והתשובה היא 0. נשמרים רק שני מספרים שלמים, ולכן הזיכרון הנוסף הוא O(1).

אלגוריתם

הגדר את result = 0.
כל עוד n גדול מ־0, חשב את הספרה האחרונה n % 10.
הגדר את result = result * 10 + digit.
הסר את הספרה באמצעות n = n / 10, תוך שימוש בחלוקה שלמה.
החזר את result.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

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

רוב הבאגים נובעים מחלוקה ומסיום הלולאה.

שימוש בחלוקה רגילה במקום שבו נדרשת חלוקה של מספרים שלמים. ב-JavaScript, ב-Python 3 וב-Lua, הביטוי n / 10 מחזיר 123.4, ולכן n לעולם לא הופך שוב למספר שלם, ו-result מתמלא בשברים. השתמשו ב-Math.floor, ב-// או בחלוקה של מספרים שלמים בשפה שלכם.
כתיבת הלולאה כך: while n >= 10. היא נעצרת לפני הספרה האחרונה, ולכן 1234 הופך ל-432.
החזרת הטקסט ההפוך בלי להמיר אותו למספר. "021" אינו המספר 21, וההשוואה לתשובה הצפויה נכשלת.
עיצוב מספר מסוג double ב-R באמצעות as.character. כאשר n מאוחסן כמספר מסוג double, הוא מוצג כך: 100000000 בתור 1e+08, והטקסט ההפוך הוא 80+e1. השתמשו ב-format(n, scientific = FALSE).

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

איך הופכים את סדר הספרות של מספר בלי להמיר אותו למחרוזת?

חזור על שני שלבים עד שהמספר הוא 0: קח את הספרה האחרונה באמצעות n % 10 והוסף אותה לתוצאה באמצעות result = result * 10 + digit, ואז הסר אותה באמצעות n = n / 10 בעזרת חילוק שלמים. עבור 1234 התוצאה גדלה כך: 4, 43, 432 ו-4321.

מה קורה לאפסים שבסוף כשמהפכים מספר?

הם יהפכו לאפסים מובילים, שאין במספר, ולכן הם נעלמים. היפוך 120 נותן 21, והיפוך 100000000 נותן 1. הלולאה האריתמטית מסירה אותם בעצמה, כי הוספת 0 לתוצאה ריקה משאירה אותה על 0.

מהי סיבוכיות הזמן של היפוך מספר שלם?

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

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

כן, כאשר הקלט יכול להיות כל מספר שלם בן 32 ביט. 1000000009 נכנס, אבל ההיפוך שלו 9000000001 לא. כאן n קטן מ־10^9, לכן להיפוך יש לכל היותר 9 ספרות והוא תמיד נכנס. בקלטים גדולים יותר, בדקו result > (INT_MAX - digit) / 10 לפני כל כפל.

Python

def reverseDigits(n):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

n = 1234

צפוי