Asteroid Collision
שורה של אסטרואידים נעה לאורך קו, כולם באותה מהירות. כל ערך ב־asteroids מתאר אסטרואיד אחד: הערך המוחלט שלו הוא הגודל שלו, והסימן שלו מציין את הכיוון שלו — חיובי לימין ושלילי לשמאל.
כאשר אסטרואיד שנע ימינה פוגש אסטרואיד שנע שמאלה, הם מתנגשים. הקטן יותר מתפוצץ; אם הם באותו גודל, שניהם מתפוצצים. אסטרואידים שנעים באותו כיוון לעולם אינם נפגשים. החזר את האסטרואידים שנשארו אחרי כל ההתנגשויות, בסדר המקורי שלהם. התוצאה יכולה להיות ריקה.
פונקציה
- asteroidsinteger-array
- האסטרואידים משמאל לימין, הסימן מציין את הכיוון, הערך המוחלט מציין את הגודל
- מחזירהinteger-array
- האסטרואידים ששרדו, משמאל לימין, ייתכן שאף אחד
אילוצים
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
דוגמאות
- קלט
- asteroids = [4, 9, -6, 2, -3]
- פלט
- [4, 9]
- הסבר
- 9 פוגש את -6 ומנצח. 2 פוגש את -3 ומתפוצץ, ואז -3 ממשיך לעוף אל 9 ומתפוצץ גם הוא. שום דבר אחר לא נע לעבר משהו, ולכן 4 ו-9 נשארים.
- קלט
- asteroids = [6, -6]
- פלט
- []
- הסבר
- 6 ו־-6 מתרסקים באותו גודל, לכן שניהם מתפוצצים והתוצאה ריקה.
- קלט
- asteroids = [-2, -7, 3, 8]
- פלט
- [-2, -7, 3, 8]
- הסבר
- -2 ו־-7 עפים שמאלה ו־3 ו־8 עפים ימינה, כך ששתי הקבוצות מתרחקות זו מזו. שום דבר לא מתנגש, וכל ארבעת האסטרואידים שורדים.
שאלת המשך
המחסנית קובעת אילו אסטרואידים שורדים. איך תדווח גם, עבור כל אסטרואיד שמתפוצץ, את האינדקס של האסטרואיד שהשמיד אותו?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התנגשות דורשת גוף שנע ימינה משמאל וגוף שנע שמאלה מימין. אסטרואיד שנע שמאלה, כשאין לפניו שום דבר שנע ימינה, בטוח לנצח. עבור לאורך השורה משמאל לימין: באילו אסטרואידים קודמים גוף חדש שנע שמאלה עדיין יכול לפגוע?
כל כלי חדש שנע שמאלה פוגע תחילה בכלי הקרוב ביותר שנע ימינה ושרד, אחר כך בכלי הבא, וכן הלאה, עד שהוא מתפוצץ או שלא נותרו כלים שנעים ימינה. הכלים ששרדו עד כה מתנהגים כמו מחסנית: רק בכלי האחרון שנוסף אפשר לפגוע עכשיו.
שמור את השורדים במחסנית. דחוף אליה כל נע ימינה. עבור נע שמאלה, כל עוד האיבר העליון הוא נע ימינה קטן יותר, הוצא אותו. אם האיבר העליון הוא נע ימינה באותו גודל, הוצא אותו והשלך את החדש. אם האיבר העליון גדול יותר, השלך את החדש. אחרת, דחוף אותו.
פתרון
אסטרואיד שנע שמאלה יכול להשמיד רצף ארוך של אסטרואידים שנעים ימינה, וכל התנגשות יכולה לחשוף זוג חדש שמתנגש מיד אחר כך. אסטרואיד חדש פוגש תמיד קודם את הניצול האחרון, ולכן מחסנית של אסטרואידים ששרדו פותרת את כל ההתנגשויות במעבר אחד.
פתור קריסה אחת בכל פעם
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
שני אסטרואידים מתנגשים בדיוק כאשר אסטרואיד שנע ימינה נמצא ישירות משמאל לאסטרואיד שנע שמאלה. מצאו את הזוג הראשון כזה, פתרו את ההתנגשות וסרקו שוב משמאל. כשלא נשאר אף זוג כזה, לא יתרחשו עוד התנגשויות והשורה היא התשובה.
סדר פתרון ההתנגשויות אינו משנה: שני אסטרואידים סמוכים הפונים זה אל זה נפגשים לפני שאחד מהם יכול לפגוש משהו אחר.
כל התנגשות דורשת סריקה חדשה והסרה מאמצע השורה. עם 9,999 אסטרואידים קטנים שנעים ימינה ואחריהם -1000, בכל סריקה עוברים לאורך השורה כדי להשמיד אסטרואיד אחד שנע ימינה: בערך 5 × 10^7 צעדים.
אלגוריתם
- העתק את השורה כדי שתוכל להסיר ממנה אסטרואידים.
- סרוק משמאל כדי למצוא את האינדקס הראשון
iשבוrow[i] > 0ו־row[i+1] < 0. - אם אין כזה, החזר את השורה.
- אחרת, הסר את הקטן מבין השניים, או את שניהם אם גודלם שווה, וסרוק שוב.
def asteroidCollision(asteroids):
row = list(asteroids)
while True:
# A crash happens where a right-mover is directly followed by a left-mover.
hit = -1
for i in range(len(row) - 1):
if row[i] > 0 and row[i + 1] < 0:
hit = i
break
if hit == -1:
return row
right, left = row[hit], -row[hit + 1]
if right > left:
del row[hit + 1]
elif right < left:
del row[hit]
else:
del row[hit:hit + 2]מחסנית של ניצולים
האינטואיציה
שומרים את האסטרואידים ששרדו עד כה במחסנית. היא לעולם אינה מכילה אסטרואיד שנע ימינה ואחריו אסטרואיד שנע שמאלה, כי הזוג הזה כבר היה מתנגש, ולכן יש בה כמה אסטרואידים שנעים שמאלה ונמלטו, ואחריהם אסטרואידים שנעים ימינה.
אסטרואיד חדש שנע ימינה עף הרחק מכל מה שנמצא במחסנית, לכן דוחפים אותו אליה. אסטרואיד חדש שנע שמאלה עף לעבר האסטרואידים שנעים ימינה ונמצאים למעלה, ופוגש קודם את החדש ביותר, לכן העליון הוא האסטרואיד היחיד שהוא יכול לפגוע בו בהמשך. בדוגמה הראשונה, -3 מוציא את 2 מהמחסנית, ואז מתפוצץ בהתנגשות עם 9, והמחסנית [4, 9] היא התשובה בסדר המקורי שלה.
כל אסטרואיד נדחף לכל היותר פעם אחת ומוצא מהמחסנית לכל היותר פעם אחת, לכן המעבר הוא O(n) גם כשאסטרואיד אחד שנע שמאלה מסלק רצף ארוך.
אלגוריתם
- התחל עם מחסנית ריקה של אסטרואידים ששרדו.
- עבור כל אסטרואיד, אם הוא נע ימינה, דחוף אותו למחסנית והמשך.
- אם הוא נע שמאלה, הוצא מהמחסנית אסטרואידים שנעים ימינה מהראש שלה, כל עוד הם קטנים ממנו.
- אם בראש המחסנית נמצא כעת אסטרואיד שנע ימינה ובגודל זהה, הוצא אותו והסר את האסטרואיד החדש. אם בראש המחסנית נמצא אסטרואיד גדול יותר שנע ימינה, הסר את האסטרואיד החדש. אחרת, דחוף אותו למחסנית.
- החזר את המחסנית מלמטה למעלה.
def asteroidCollision(asteroids):
survivors = [] # the row so far, after every crash it caused
for rock in asteroids:
alive = True
# Only a left-mover can hit something: a right-mover on top of the stack.
while alive and rock < 0 and survivors and survivors[-1] > 0:
top = survivors[-1]
if top < -rock:
survivors.pop() # the right-mover is smaller and explodes
elif top == -rock:
survivors.pop() # same size: both explode
alive = False
else:
alive = False # the right-mover is bigger: the new one explodes
if alive:
survivors.append(rock)
return survivors
מלכודות ומקרי קצה
- התייחסות לנע ימינה שבא אחרי נע שמאלה כאילו התנגשו. ב־
[-2, -7, 3, 8]הקבוצות מתרחקות זו מזו, וכל הארבעה שורדים. - שימוש ב־
ifבמקום ב־whileעבור ההוצאות מהמחסנית. ב־[1, 2, 3, 4, 5, -15]הנע שמאלה משמיד את כל חמשת הנעים ימינה ושורד. - התעלמות ממקרה השוויון. ב־
[6, -6]צריך להוציא את 6 ולהשליך את -6, כך שהתוצאה תהיה ריקה. - דחיפת נע שמאלה שהפסיד. ב־
[9, -6], -6 מתפוצץ ואסור שיונח על המחסנית; יש לשמור דגל שמציין אם הוא עדיין בחיים.
שאלות נפוצות3
מהי סיבוכיות הזמן של Asteroid Collision?
סיבוכיות זמן O(n) וסיבוכיות מקום O(n) עם מחסנית של אסטרואידים ששרדו, מכיוון שכל אסטרואיד נדחף ונשלף לכל היותר פעם אחת. סריקה מחדש של השורה אחרי כל התנגשות עולה O(n²).
למה מחסנית היא מבנה הנתונים המתאים להתנגשות אסטרואידים?
אסטרואיד חדש יכול להגיע רק לניצולים הקרובים אליו ביותר, והוא פוגש אותם מהחדש ביותר לישן ביותר. זהו האחרון שנכנס, הראשון שיוצא. כל מה שנמצא במחסנית בסוף כבר לא יכול להתרסק, ולכן זו השורה האחרונה.
האם אפשר לפתור את התנגשות האסטרואידים ב־O(1) של מקום נוסף?
כן, אם מותר לך לדרוס את הקלט. השתמש בתחילת המערך בתור המחסנית: שמור אינדקס כתיבה top, השווה מול asteroids[top-1], והחזר את top האיברים הראשונים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def asteroidCollision(asteroids):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
asteroids = [4, 9, -6, 2, -3]
הפלט הצפוי
[4, 9]