Remove Nth Node From End of List
ניתנת לך רשימה מקושרת חד־כיוונית המאוחסנת בשני מערכים באותו אורך. הצומת i מכיל את הערך values[i] ומצביע לצומת next[i], -1 מסיים את הרשימה, והראש הוא צומת 0. הצמתים אינם מאוחסנים לפי סדר הרשימה, לכן יש לעקוב אחר הקישורים.
הסר את הצומת ה־n בספירה מסוף הרשימה, כאשר הצומת האחרון הוא הראשון מסוף הרשימה. החזר את הערכים של הצמתים שנותרו, לפי סדר הרשימה.
פונקציה
- valuesinteger-array
- הערך שמוחזק בכל צומת
- nextinteger-array
- האינדקס של הצומת שאליו כל צומת מקושר, או -1 עבור הצומת האחרון
- ninteger
- איזה צומת להסיר, בספירה מסוף הרשימה, כאשר 1 הוא הצומת האחרון
- מחזירהinteger-array
- הערכים הנותרים לפי הסדר ברשימה, ריק כאשר מסירים את הצומת היחיד
אילוצים
1 ≤ L ≤ 5000, כאשרLהוא האורך שלvaluesושלnext.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- כל
next[i]הוא-1או אינדקס של צומת מ־0עדL-1. - החל בצומת
0, הרשימה מבקרת בכל צומת פעם אחת בדיוק ואז מגיעה אל-1. אין מעגל.
דוגמאות
- קלט
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- פלט
- [5, 2, 6, 7]
- הסבר
- מעקב אחר הקישורים החל מצומת
0עובר בצמתים0, 2, 4, 1, 3, ולכן הרשימה היא5, 2, 6, 9, 7. הצומת השני מהסוף הוא צומת1, שערכו9, ובלעדיו הרשימה היא5, 2, 6, 7. האיבר במערךvalues[5-2] = 7הוא הצומת האחרון, ולא זה שיש להסיר.
- קלט
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- פלט
- [20, 30, 40]
- הסבר
- ארבעה צמתים ו־
n = 4: הצומת הרביעי מהסוף הוא הראש. הרשימה מתחילה עכשיו בצומת1ונקראת20, 30, 40.
- קלט
- values = [42]next = [-1]n = 1
- פלט
- []
- הסבר
- הצומת היחיד הוא גם הראש וגם הצומת האחרון. הסרתו משאירה רשימה ריקה, ולכן התשובה היא
[].
+14 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל למצוא את הצומת ולנתק אותו במעבר אחד, בלי לספור תחילה את האורך?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
רשימה מתקדמת רק קדימה, והצומת מוגדר לפי המרחק שלו מהסוף. אילו ידעת את האורך
L, באיזה מיקום מההתחלה הוא היה נמצא? ואת הקישור של איזה צומת צריך לשנות כדי להוציא אותו?אפשר למדוד את המרחק עד לסוף בלי לדעת את האורך. מקדמים מצביע אחד
nחוליות לפני האחר ומזיזים אותם יחד. כשהמוביל עומד על הצומת האחרון, המצביע הנגרר עומד ממש לפני הצומת שיש להסיר.קדם את
fastnפעמים. אם הוא כעת-1, הראש הוא הצומת שיש להסיר, ולכן הרשימה מתחילה ב־next[0]. אחרת, קדם אתslowואתfastיחד כל עודnext[fast] != -1, ואז הגדרnext[slow] = next[next[slow]]. עבור על הרשימה מהראש ואסוף את הערכים.
פתרון
היעד מוגדר לפי המרחק שלו מהסוף, אבל רשימה מקושרת חד־כיוונית מאפשרת לך להתקדם רק קדימה, ואתה לומד היכן נמצא הסוף רק כשאתה מגיע אליו. כדי להסיר צומת, צריך גם לעמוד על הצומת שלפניו, כי הקישור של אותו צומת הוא זה שמשתנה. אפשר להעתיק את הרשימה למערך, או לספור את הצמתים ולעבור שוב על הרשימה. הפתרון הקלאסי מחזיק שני מצביעים במרחק של n קישורים זה מזה, כך שכשהמצביע הקדמי מגיע לצומת האחרון, המצביע האחורי נמצא ממש לפני היעד. בהמשך, L הוא מספר הצמתים.
העתק את הערכים למערך
האינטואיציה
בבעיה הזו מצביע הוא אינדקס של צומת. התקדמות קדימה היא node = next[node], והגעה אל -1 פירושה שיצאת מקצה הרשימה. בדוגמה הראשונה, המעבר מהצומת 0 הוא 0 → 2 → 4 → 1 → 3 → -1.
ספירה מהסוף קשה רק משום שלרשימה אין מיקומים. לכן נותנים לה מיקומים: עוברים עליה פעם אחת ומוסיפים כל ערך למערך. בדוגמה הראשונה המערך הוא [5, 2, 6, 9, 7]. במערך של L ערכים, האחרון נמצא באינדקס L-1, ולכן הערך ה-n מהסוף נמצא באינדקס L-n. כאן זה 5-2 = 3, הערך 9. מוחקים אותו ומחזירים את [5, 2, 6, 7].
הפתרון הזה נכון ופועל בזמן O(L), אבל הוא מעתיק את הרשימה כולה ואינו נוגע בקישורים. מטרת הבעיה היא לערוך את הרשימה עצמה, באמצעות זיכרון נוסף של O(1), וזה מה שעושות שתי הגישות הבאות.
אלגוריתם
- התחילו עם מערך ריק ועם
node = 0. - כל עוד
nodeאינו-1, הוסיפו אתvalues[node]ועברו אלnext[node]. - מחקו את האיבר באינדקס
length - n. - החזירו את המערך.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderספור את הצמתים, ואז נתק
האינטואיציה
כדי להסיר צומת מרשימה, משנים את הקישור של הצומת שלפניו כך שידלג מעליו: next[prev] = next[next[prev]]. הצומת שהוסר עדיין נמצא במערכים, אבל שום מעבר מהראש כבר לא יגיע אליו.
לכן מצאו את prev. ספרו את הצמתים במעבר הראשון. אם סופרים את הראש כמיקום 0, היעד נמצא במיקום L-n והצומת שלפניו במיקום L-n-1, שאליו מגיעים מהראש אחרי L-n-1 צעדים. בדוגמה הראשונה L = 5 ו-n = 2: שני צעדים 0 → 2 → 4 מביאים אתכם לצומת 4, שמקושר לצומת 1, כלומר ל-9. הגדרת next[4] = next[1] = 3 גורמת לרשימה להציג 5, 2, 6, 7.
יש מקרה אחד שבו אין צומת לפני היעד: n = L, כשהיעד הוא הראש. במקרה כזה אין צורך לשנות קישורים. הרשימה מתחילה ב-next[0] במקום ב-0, כמו בדוגמה השנייה. לאחר מכן עברו על הרשימה מהראש כדי לאסוף את התשובה. שני מעברים על הרשימה עולים בערך 2L צעדים, והזיכרון הנוסף מעבר לתשובה מסתכם בכמה מספרים שלמים.
אלגוריתם
- עוברים מהצומת
0אל-1וסופרים את הצמתים בתורL. - אם
n == L, הראש החדש הואnext[0]. - אחרת, מתחילים את
prevבצומת0ומקדמים אותוL-n-1פעמים, ואז מציביםnext[prev] = next[next[prev]]. - עוברים מהראש ואוספים את
values[node]לפי הסדר.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultשני מצביעים המרוחקים זה מזה ב-n קישורים
האינטואיציה
אפשר למדוד ״n מהסוף״ בלי לדעת את L. מקדמים את fast ב־n קישורים בזמן ש־slow ממתין בראש. לאחר מכן מקדמים את שניהם קישור אחד בכל פעם. המרווח נשאר n, ולכן כש־fast עומד בצומת האחרון (next[fast] == -1, במיקום L-1), slow עומד במיקום L-1-n: הצומת שלפני צומת היעד. פעולת next[slow] = next[next[slow]] אחת מסירה את צומת היעד.
עקבו אחר הדוגמה הראשונה. fast מתקדם שני צעדים, 0 → 2 → 4. עכשיו שניהם מתקדמים: slow מגיע ל־2 בזמן ש־fast מגיע ל־1, ואז slow מגיע ל־4 בזמן ש־fast מגיע ל־3. צומת 3 הוא האחרון, ולכן עוצרים. next[4] הוא צומת 1, ה־9, והצבת next[4] = next[1] = 3 מסירה אותו.
המקרה של הראש מתגלה מעצמו. מכיוון ש־n ≤ L, fast מגיע ל־-1 במהלך ההתקדמות ההתחלתית שלו רק כאשר n = L, וזה בדיוק המקרה שבו הראש הוא צומת היעד. עם אובייקטים של צמתים, הייתם מציבים צומת דמה לפני הראש כדי להעלים את המקרה הזה; כאן הבדיקה fast == -1 עושה את אותה עבודה. איתור הצומת וניתוקו דורשים מעבר אחד. כתיבת התשובה דורשת הליכה נוספת, שכל גישה צריכה.
אלגוריתם
- הגדר את
fast = 0והתקדם איתוnפעמים באמצעותfast = next[fast]. - אם
fast == -1, הראש הוא היעד: הראש החדש הואnext[0]. - אחרת, הגדר את
slow = 0והתקדם עם שניהם כל עודnext[fast] != -1. - הגדר את
next[slow] = next[next[slow]]. - התקדם מהראש ואסוף את
values[node]לפי הסדר.
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
מלכודות ומקרי קצה
רוב התשובות השגויות נובעות מהמקום שבו המצביע העוקב נעצר ומהמקרה שבו הראש מוסר.
- הסרת האיבר באינדקס
L-nשל המערך. הצמתים אינם מאוחסנים לפי סדר הרשימה, ולכן האינדקס הזה מצביע בדרך כלל על צומת אחר. בדוגמה הראשונהvalues[3] = 7הוא הצומת האחרון, ולא9. - עצירה כאשר
fast == -1במקום כאשרnext[fast] == -1. כךslowמתקדם צעד אחד רחוק מדי, אל צומת היעד עצמו, וברשימה מקושרת חד-כיוונית אי אפשר לנתק צומת מתוך הצומת עצמו. - שכחת הטיפול במקרה של הראש. כאשר
n = L, הערך שלfastהוא-1אחרי ההתחלה שלו מהראש, וקריאה שלnext[fast]גורמת לקריסה ברוב השפות. Python קוראת אתnext[-1]בלי להתלונן ומחזירה רשימה שגויה, שקשה יותר לזהות. - ניתוק באמצעות
next[slow] = next[slow] + 1אוslow + 2. צמתים שכנים ברשימה אינם שכנים במערכים; הדרך היחידה להגיע לצומת שאחרי היעד היאnext[next[slow]]. - איסוף התשובה מהצומת
0אחרי שהראש הוסר. התחילו את המעבר הסופי מהראש החדש. - שכחת ההיסט ב-Lua וב-R, שבהן המערכים מתחילים ב-1. השאירו את אינדקסי הצמתים מבוססי-0 וקראו את
next[node + 1]. Ruby ו-R שומרות את המילהnext, ולכן בפתרונות הפתיחה שלהן שם הפרמטר הואnext_.
שאלות נפוצות4
איך מסירים את הצומת ה-n מהסוף של רשימה מקושרת במעבר אחד?
השתמש בשני מצביעים עם פער של n. קדם את הראשון ב־n צמתים, ואז התקדם עם שניהם יחד עד שהראשון נמצא בצומת האחרון. השני נמצא כעת ממש לפני הצומת שיש להסיר, ולכן מפנים את הקישור שלו אל מעבר לצומת הזה. אם המצביע הראשון יוצא מהרשימה במהלך ההתקדמות הראשונית שלו, הצומת שיש להסיר הוא ראש הרשימה.
למה הפתרונות לבעיה הזאת משתמשים בצומת דמה?
הסרת צומת פירושה שינוי הקישור של הצומת שלפניו, ולראש אין צומת לפניו. צומת דמה שמוצב לפני הראש נותן לכל צומת, כולל הראש, צומת קודם, כך ששורת ניתוק אחת מטפלת בכל המקרים. התשובה מתחילה אז בצומת הבא של צומת הדמה. בדיקה אם המצביע המוביל יצא מהרשימה אחרי n צעדים מטפלת באותו מקרה ללא הצומת הנוסף.
מהי סיבוכיות הזמן והמקום של הסרת הצומת ה־nth מהסוף?
נדרשים O(L) זמן עבור רשימה של L צמתים, מכיוון שצריך להגיע לסוף כדי לדעת היכן נמצא היעד. גם ספירה תחילה וגם שיטת שני המצביעים משתמשות בזיכרון נוסף של O(1). העתקת הערכים למערך דורשת O(L).
האם הפתרון עם שני מצביעים מהיר יותר מאשר ספירת האורך תחילה?
לא בהרבה: שניהם O(L), ושני המצביעים יחד עדיין מבצעים בערך את אותו מספר מהלכים כמו שתי סריקות. היתרון האמיתי הוא שאין צורך לדעת את האורך מראש, ולכן השיטה עובדת גם כשהרשימה מגיעה כזרם שאפשר לקרוא רק פעם אחת. זה בדיוק מה שמראיינים בדרך כלל מבקשים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def removeNthFromEnd(values, next, n):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
צפוי
[5, 2, 6, 7]