Palindrome Number
מספר הוא פלינדרום כאשר הספרות שלו נקראות אותו דבר משמאל לימין ומימין לשמאל, כמו 1221. בהינתן מספר שלם x, החזר true אם הוא פלינדרום ו-false אחרת. מספר שלילי לעולם אינו נחשב, כי לסימן המינוס שלו אין סימן תואם בקצה השני.
פונקציה
- xinteger
- המספר השלם לבדיקה, שעשוי להיות שלילי
- מחזירהboolean
- true אם x נקרא אותו הדבר בשני הכיוונים, false אחרת
אילוצים
-231 ≤ x ≤ 231-1- כל מספר שלילי מחזיר
false.
דוגמאות
- קלט
- x = 121
- פלט
- true
- הסבר
- כשקוראים אותו לאחור, 121 עדיין נשאר 121, ולכן התשובה היא
true.
- קלט
- x = -121
- פלט
- false
- הסבר
- בקריאה לאחור,
-121הופך ל־121-, וזה טקסט שונה, לכן התשובה היאfalse.
שאלת המשך
האם תוכל לפתור את זה בלי להמיר את המספר השלם למחרוזת?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
מספרים שליליים לעולם אינם יכולים להיות פלינדרומים, לכן טפל בהם קודם.
קח את הספרה האחרונה באמצעות
x % 10והסר אותה באמצעות חילוק שלם ב־10.בנו את המספר ההפוך באמצעות
reversed = reversed * 10 + digit, ואז השוו אותו למספר המקורי.
פתרון
מספר הוא פלינדרום כאשר הוא שווה למספר שמתקבל בהיפוך הספרות שלו. כמחרוזת, זו השוואה אחת. בלי להשתמש במחרוזת, בנייה מחדש של המספר כולו בסדר הפוך עלולה לגרום לגלישה, לכן הופכים רק את המחצית השנייה של הספרות ומשווים אותה למחצית הראשונה.
השווה את המחרוזת למחרוזת ההפוכה שלה
האינטואיציה
כתבו את המספר כטקסט והשוו אותו להפוך שלו. מספרים שליליים אינם דורשים טיפול מיוחד: -121 מתחיל בסימן מינוס ומסתיים בספרה, ולכן הוא לעולם אינו שווה להפוך שלו 121-.
בטקסט יש תו אחד לכל ספרה, בערך log10(x) תווים ולא יותר מ־11 במקרה הזה. העלות היא המחרוזת הנוספת.
אלגוריתם
- המירו את
xלמחרוזתs. - הפכו את
s. - החזירו האם
sשווה להיפוך שלו.
def isPalindrome(x):
s = str(x)
# A minus sign sits only at the front, so a negative never matches its reverse.
return s == s[::-1]הפוך חצי מהמספר
האינטואיציה
x % 10 נותן את הספרה האחרונה, וחילוק שלם ב־10 מסיר אותה. העברת ספרות מסוף x למספר שני, half, יוצרת את ההיפוך של הספרות שהסרת. עצור כש־half גדול או שווה למה שנותר ב־x: לקחת חצי מהספרות. המספר 1221 מסתיים כך: x = 12 ו־half = 12, וזה פלינדרום. כשיש מספר אי־זוגי של ספרות, half מכיל גם את הספרה האמצעית: המספר 12321 מסתיים כך: x = 12 ו־half = 123, ולכן משווים את x ל־half / 10.
טפל בשני מקרים לפני הלולאה. מספר שלילי לעולם אינו פלינדרום. מספר שמסתיים ב־0 חייב להתחיל ב־0, ורק 0 עצמו עושה זאת; ללא הבדיקה הזו, המספר 10 מסתיים כך: x = 0 ו־half = 1, והתנאי x == half / 10 מתקיים בטעות. half לעולם לא יגדל מעבר ל־6 ספרות, ולכן הוא מתאים לכל טיפוס שלם.
אלגוריתם
- אם
xשלילי, או מסתיים ב־0 ואינו 0, החזרfalse. - הגדר
half = 0. - כל עוד
x > half, הגדרhalf = half * 10 + x % 10וחלק אתxב־10 בחלוקה שלמה. - החזר
trueאםx == half(מספר זוגי של ספרות) אוx == half / 10(מספר אי־זוגי של ספרות).
def isPalindrome(x):
if x < 0:
return False
original, reversed_num = x, 0
while x > 0:
reversed_num = reversed_num * 10 + x % 10
x //= 10
return original == reversed_num
מלכודות ומקרי קצה
- שכחת שליליים. בשפות שבהן השארית שומרת על הסימן, היפוך
-121נותן-121והבדיקה עוברת. ב-Python, שבה-1 // 10הוא-1, לולאתwhile x != 0לעולם לא מסתיימת. - אי-דחייה של מספרים שמסתיימים ב-0. היפוך החצי מקבל אז את
10.0עצמו הוא פלינדרום. - היפוך המספר כולו במספר שלם של 32 סיביות. ההיפוך של
2147483647לא נכנס לטווח. - שימוש ב-
/בשפה שמבצעת חילוק עם שבר. השתמשו ב-Math.floor(x / 10)ב-JavaScript, ב-//ב-Python, ב-%/%ב-R וב-~/ב-Dart. - השוואת ההיפוך המלא ל-
xלאחר שהלולאה שינתה אתx. שמרו עותק של הערך המקורי.
שאלות נפוצות3
האם מספר שלילי הוא פלינדרום?
לא. כשקוראים בכיוון ההפוך, -121 הופך ל־121-, ולסימן המינוס אין תו תואם בקצה השני. לכן כל מספר שלם שלילי מחזיר false.
למה להפוך רק חצי מהמספר?
היפוך של כל ספרה עלול לגרום לגלישת יתר במספר שלם בן 32 סיביות: המספר ההפוך של 2147483647 גדול מהערך המרבי של int. מחצית מהספרות תמיד נכנסת בטווח, והלולאה מבצעת מחצית מהעבודה.
מהי סיבוכיות הזמן של Palindrome Number?
שתי הגישות פועלות בזמן O(log x), כי למספר x יש בערך log10(x) ספרות, וכל אחת מהן מטופלת פעם אחת. גישת המחרוזת משתמשת במקום נוסף של O(log x) עבור הטקסט; היפוך החצי משתמש במקום של O(1).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def isPalindrome(x):
# כתבו כאן קודבדיקה #1
בדיקה #2
ארגומנט
x = 121
הפלט הצפוי
true