Add Two Numbers
נתונים לך שני מספרים שלמים לא־שליליים, שכל אחד מהם מאוחסן כרשימה מקושרת חד־כיוונית של הספרות שלו, כשהספרה הפחות משמעותית מופיעה ראשונה. ברשימה הראשונה, הצומת i מכיל את הספרה values1[i] ומקושר לצומת next1[i]. הרשימה השנייה פועלת באותו אופן, עם next2 ו-values2. בשתי הרשימות, -1 מסיים את הרשימה, והראש הוא צומת 0. הצמתים אינם מאוחסנים לפי סדר הרשימה, לכן יש לעקוב אחר הקישורים.
החזר את ספרות הסכום של שני המספרים, כשהספרה הפחות משמעותית מופיעה ראשונה.
פונקציה
- next1integer-array
- האינדקס של הצומת שאליו מקושר כל צומת של המספר הראשון, או -1 עבור הצומת האחרון שלו
- values1integer-array
- הספרה שמוחזקת בכל צומת של המספר הראשון
- next2integer-array
- האינדקס של הצומת שאליו מקושר כל צומת של המספר השני, או -1 עבור הצומת האחרון שלו
- values2integer-array
- הספרה שמוחזקת בכל צומת של המספר השני
- מחזירהinteger-array
- הספרות של הסכום, מהפחות משמעותית תחילה
אילוצים
1 ≤ L1 ≤ 100, כאשרL1הוא האורך שלnext1ושלvalues1.1 ≤ L2 ≤ 100, כאשרL2הוא האורך שלnext2ושלvalues2.0 ≤ values1[i], values2[j] ≤ 9- כל איבר של
next1הוא-1או אינדקס של צומת ברשימה הראשונה, וכל איבר שלnext2הוא-1או אינדקס של צומת ברשימה השנייה. - החל מהצומת
0, כל רשימה עוברת בכל אחד מהצמתים שלה בדיוק פעם אחת ואז מגיעה אל-1. אין מחזור. - לאף מספר אין אפסים מובילים: הצומת האחרון ברשימה מכיל ספרה שאינה
0, אלא אם הרשימה מכילה את הספרה היחידה0.
דוגמאות
- קלט
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- פלט
- [5, 4, 1, 1]
- הסבר
- הרשימה הראשונה עוברת בצמתים
0, 2, 1וקוראת8, 1, 6, כלומר את המספר 618. השנייה קוראת7, 2, 5, כלומר את המספר 527. הסכום שלהם הוא 1145, ולכן התשובה היא5, 4, 1, 1.
- קלט
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- פלט
- [0, 0, 0, 0, 1]
- הסבר
- הרשימה השנייה נקראת
1, 9, 9, 9, המספר 9991. הוספת 9 נותנת 10000: כל עמודה מפיקה0ונשיאה, והנשיאה האחרונה הופכת לספרה חמישית.
- קלט
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- פלט
- [7, 5]
- הסבר
- המספר הראשון הוא 0 והרשימה השנייה נקראת
7, 5, המספר 57. הוספת 0 אינה משנה דבר, לכן התשובה היא[7, 5].
שאלת המשך
איך היית מחבר את המספרים אם הרשימות היו מאחסנות את הספרה המשמעותית ביותר ראשונה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
המרת כל רשימה למספר נכשלת: 100 ספרות אינן נכנסות לאף סוג של מספר שלם. איך מחברים שני מספרים ארוכים על נייר?
הרשימות מתחילות בספרת האחדות, בדיוק במקום שבו מתחיל חיבור בעמודות. כל עמודה מחברת ספרה אחת מכל מספר, יחד עם הנשיאה מהעמודה הקודמת. העמודה כותבת
sum % 10ונושאת אתsum / 10, בעיגול כלפי מטה.עבור על שתי הרשימות בו־זמנית, עם מצביע אחד לכל רשימה. לרשימה שהסתיימה מוסיפים
0. ממשיכים כל עוד אחד מהמצביעים אינו-1או שהנשיאה היא1, כך שנשיאה סופית הופכת לספרה נוספת.
פתרון
המספרים ארוכים מדי עבור כל טיפוס מספר שלם, לכן חברו אותם כמו על נייר: עמודה אחר עמודה, והעבירו 1 כשעמודה מגיעה ל־10. הרשימות מאחסנות קודם את ספרת האחדות, לכן מעבר עליהן עובר בעמודות לפי הסדר שבו מחברים אותן.
העתיקו את הספרות החוצה, ואז חברו עמודה אחר עמודה
האינטואיציה
מצביע כאן הוא אינדקס של צומת, והתקדמות קדימה היא node = next[node]. העתיקו את הספרות של כל רשימה למערך, כך שאינדקס i יכיל את הספרה שערכה 10^i: [8, 1, 6] ו-[7, 2, 5] בדוגמה הראשונה.
לאחר מכן חברו כמו על נייר, והתייחסו לספרה חסרה כאל 0. בכל עמודה כותבים sum % 10 ומעבירים את השארית: 8 + 7 = 15 כותבים 5 ומעבירים 1, 1 + 2 + 1 = 4, ו-6 + 5 = 11 כותבים 1. ההעברה האחרונה הופכת לספרה סופית: [5, 4, 1, 1].
ההעתקים צורכים זיכרון נוסף של O(L1 + L2), שהחיבור כלל אינו זקוק לו.
אלגוריתם
- עבור על כל רשימה החל מהצומת
0והעתק את הספרות שלה למערך. - הגדר
carry = 0. עבור כל אינדקסiעד לאורך המערך הארוך יותר, חבר את הספרות שבאינדקסi, אם הן קיימות, ואת הערך שב־carry. - הוסף את
sum % 10והגדר אתcarryל־sum / 10, בעיגול כלפי מטה. - אם הערך שב־carry הוא
1אחרי העמודה האחרונה, הוסף אותו.
def readDigits(next, values):
# The digits in list order: least significant first.
digits = []
node = 0
while node != -1:
digits.append(values[node])
node = next[node]
return digits
def addTwoNumbers(next1, values1, next2, values2):
first = readDigits(next1, values1)
second = readDigits(next2, values2)
result = []
carry = 0
for i in range(max(len(first), len(second))):
column = carry
if i < len(first):
column += first[i]
if i < len(second):
column += second[i]
result.append(column % 10)
carry = column // 10
if carry > 0:
result.append(carry)
return resultעבור על שתי הרשימות בו־זמנית עם נשא
האינטואיציה
העמודה i משתמשת רק בצומת ה־i בכל רשימה, לכן שמור מצביע אחד לכל רשימה, a ו־b, וקדם את שניהם ככל שמתקדמים בעמודות.
לולאה אחת פועלת כל עוד a אינו -1, או b אינו -1, או שהנשיאה היא 1. מצביע שעדיין יש לו צומת מוסיף את הספרה שלו ומתקדם; מצביע שנמצא ב־-1 אינו מוסיף דבר. כך מטפלים במספרים באורכים שונים בלי לולאה שנייה, ותנאי הנשיאה כותב את הספרה הנוספת בסוף.
בדוגמה השנייה, 9 ועוד 9991, כל עמודה מסתכמת ב־10 וכותבת 0. אחרי ארבע עמודות שתי הרשימות מסתיימות, אבל הנשיאה היא 1, ולכן הלולאה פועלת פעם נוספת: [0, 0, 0, 0, 1]. מלבד התשובה, היא מחזיקה שלושה מספרים שלמים.
אלגוריתם
- הגדר את
a = 0, אתb = 0ואתcarry = 0. - כל עוד
a != -1אוb != -1אוcarry > 0, התחל את סכום העמודה בערךcarry. - אם
a != -1, הוסף אתvalues1[a]והגדר אתa = next1[a]. עשה את אותו הדבר עבורbעם הרשימה השנייה. - הוסף את
sum % 10והגדר אתcarryל-sum / 10, בעיגול כלפי מטה. - החזר את הספרות שהוספת.
def addTwoNumbers(next1, values1, next2, values2):
a = 0 # current node of the first number
b = 0 # current node of the second number
carry = 0
result = []
# Keep going while either number has digits left or a carry is waiting.
while a != -1 or b != -1 or carry > 0:
column = carry
if a != -1:
column += values1[a]
a = next1[a]
if b != -1:
column += values2[b]
b = next2[b]
result.append(column % 10) # the digit this column writes
carry = column // 10 # 1 when the column reached 10, else 0
return result
מלכודות ומקרי קצה
- המרת כל רשימה למספר שלם וחיבורן. מספר בן 100 ספרות חורג מהטווח של כל טיפוס בן 64 סיביות.
- השמטת הנשיאה הסופית. לולאה שעוצרת כששתי הרשימות מסתיימות מחזירה
[0, 0, 0, 0]עבור הדוגמה השנייה. - עצירה כשמסתיימת הרשימה הקצרה יותר. כך הדוגמה השנייה מאבדת את שלוש הספרות 9 של 9991 ואת הנשיאה שעוברת דרכן.
- קריאת הספרות לפי סדר המערך. בדוגמה הראשונה,
values1הוא[8, 6, 1], אבל המספר הוא 618, כשקוראים לאורך הקישורים. - שכחת ההיסט ב-Lua וב-R, שבהן המערכים מתחילים ב-1. השאר את מזהי הצמתים מבוססי 0, וקרא את
next1[node + 1].
שאלות נפוצות3
למה הספרות מאוחסנות בסדר הפוך ב־Add Two Numbers?
החיבור מתחיל בספרת האחדות, ואפשר לעבור ברשימה מקושרת חד־כיוונית רק מהראש שלה. כשהספרה הפחות משמעותית מופיעה ראשונה, המעבר מבקר בעמודות לפי סדר החיבור שלהן, כך שהנשיאה מתקדמת יחד עם המצביעים.
מהי סיבוכיות הזמן של חיבור שני מספרים המאוחסנים ברשימות מקושרות?
זה O(max(L1, L2)): צעד אחד לכל עמודה, ועוד צעד אחד אם נשארת נשיאה בסוף. מלבד התשובה, הגרסה במעבר יחיד משתמשת בזיכרון של O(1): שני מצביעים והנשיאה.
האם הנשיאה יכולה אי פעם להיות גדולה מ־1?
לא. עמודה מחברת שתי ספרות שערכן לכל היותר 9 ונשיאה שערכה לכל היותר 1, ולכן הסכום שלה הוא לכל היותר 19. חלוקה ב־10 ועיגול כלפי מטה נותנים 0 או 1.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def addTwoNumbers(next1, values1, next2, values2):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
הפלט הצפוי
[5, 4, 1, 1]