Last Stone Weight

Q: מהי סיבוכיות הזמן של Last Stone Weight?

בעזרת ערימת מקסימום, בניית הערימה ומשחק של לכל היותר n-1 סבבים, שבכל אחד מהם מבצעים שתי שליפות והכנסה אחת, אורכים O(n log n) זמן ודורשים O(n) מקום. מיון כל הערימה בכל סבב במקום זאת אורך O(n² log n) .

קלערימה

+10

יש לך ערימת אבנים, ו-stones[i] הוא המשקל של אבן i. בכל סיבוב, קח את שתי האבנים הכבדות ביותר ורסק אותן זו בזו. אם משקליהן זהים, שתיהן מושמדות. אחרת, האבן הקלה יותר מושמדת והאבן הכבדה יותר מצטמצמת להפרש בין שני המשקלים.

כתוב פונקציה בשם lastStoneWeight שממשיכה לשחק סיבובים עד שנותרת לכל היותר אבן אחת, ומחזירה את משקל האבן הזאת, או 0 כשלא נותרות אבנים.

פונקציה

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: המשקלים של האבנים בערימה
מחזירהinteger: המשקל של האבן האחרונה, או 0 אם לא נותרה אף אחת

אילוצים

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

דוגמאות

קלט: stones = [3, 9, 4, 6, 2]
פלט: 0
הסבר: 9 ו־6 משאירים 3, ואז 4 ו־3 משאירים 1, ואז 3 ו־2 משאירים עוד 1. שתי האבנים במשקל 1 משמידות זו את זו, ולכן לא נשאר דבר והתשובה היא 0.

קלט: stones = [10, 4, 1]
פלט: 5
הסבר: 10 ו-4 משאירים 6, ו-6 ו-1 משאירים 5. אבן אחת נותרת, במשקל 5.

קלט: stones = [8]
פלט: 8
הסבר: אין אבן אחרת שאפשר לרסק אבן בודדת נגדה, ולכן משקלה 8 הוא התשובה.

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

שאלת המשך

המשקלים הם לכל היותר 1000. האם תוכלו לנצל את החסם הזה כדי לסיים בזמן O(n + W), כאשר W הוא המשקל הגדול ביותר, בלי ערימה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

מיין את הערימה בכל סיבוב

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

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

ההפרש יכול להגיע לכל מקום בסדר. בדוגמה הראשונה, 9 ו־6 משאירים 3, שצריך להיות לפני 4, ולכן ממיינים שוב לפני הסיבוב הבא כדי למצוא את שתי האבנים הכבדות ביותר החדשות.

בכל סיבוב מוסרת לפחות אבן אחת, לכן יש עד n-1 סיבובים, שבכל אחד מהם ממיינים עד n אבנים: O(n² log n). כאשר n = 10^4, מדובר בכ־10^4 פעולות מיון של עד 10^4 מספרים, כלומר לפחות 5 × 10^7 צעדים גם כשהמיון מזהה שהרשימה כמעט ממוינת, וכמה פעמים יותר כשהוא לא. זה איטי מדי עבור הבדיקות הגדולות ביותר, בעוד שהערימה שבהמשך דורשת רק כמה מאות אלפי צעדים.

אלגוריתם

העתק את האבנים לרשימה בשם pile.
כל עוד יש בערימה יותר מאבן אחת, מיין אותה בסדר עולה.
הוצא את שתי האבנים האחרונות, heaviest ו־second.
אם הן שונות, הוסף בחזרה לערימה את heaviest - second.
החזר את האבן שנותרה, או את 0 כשהערימה ריקה.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

ערימת מקסימום

האינטואיציה

בכל סיבוב צריך רק את האבנים הגדולות ביותר, ולא את הסדר המלא. ערימת מקסימום נועדה בדיוק לכך: היא שומרת את הערך הגדול ביותר בראש, והסרה של הערך שבראש או הוספת ערך עולות O(log n).

הכניסו כל אבן לערימה. בכל סיבוב, שלפו פעמיים כדי לקבל את שתי האבנים הכבדות ביותר. אם הן שונות, דחפו את ההפרש בחזרה; הערימה תעביר אותו למקום הנכון בעצמה. עבור [10, 4, 1] שולפים את 10 ואת 4 ודוחפים את 6, ואז שולפים את 6 ואת 1 ודוחפים את 5, ובערימה נשאר רק 5.

יש לכל היותר n-1 סיבובים, ובכל אחד מהם שתי שליפות ולכל היותר דחיפה אחת, לכן זמן הריצה הוא O(n log n) והערימה משתמשת ב-O(n) מקום. בחלק מהשפות יש ערימה מובנית: heapq של Python היא ערימת מינימום, ולכן היא שומרת משקלים שליליים; ל-Java יש PriorityQueue, ל-C++ יש priority_queue, ל-Go יש container/heap, ל-Rust יש BinaryHeap ול-PHP יש SplMaxHeap. בשפות האחרות הפתרון מממש ערימה משלו במערך: ההורה של האינדקס i נמצא ב-(i-1)/2, וערך חדש מטפס כלפי מעלה כל עוד הוא גדול מההורה שלו.

אלגוריתם

הכניסו כל אבן לערמת מקסימום.
כל עוד הערמה מכילה יותר מאבן אחת, שלפו את האבן הכבדה ביותר ואז את האבן השנייה בכובדה.
אם משקליהן שונים, הכניסו לערמה את heaviest - second.
החזירו את ראש הערמה, או את 0 אם היא ריקה.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

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

הסימולציה קצרה, ולכן הבאגים מסתתרים בקצוות ובערימה עצמה.

החזרת הערך העליון מערימה ריקה. כאשר משקלן של שתי האבנים האחרונות זהה, לא נשאר כלום והתשובה היא 0.
שימוש בטעות בערימת מינימום. heapq של Python ו-PriorityQueue כברירת מחדל של Java מחזירות את הערך הקטן ביותר; יש להפוך את סימן המשקלים או להעביר משווה בסדר הפוך.
שכחה להפוך את הסימן בחזרה. עם heapq, שני הערכים שנשלפו שליליים, ולכן ההפרש שמכניסים הוא -(heaviest - second).
מיון פעם אחת בתחילת הדרך ומעבר על הרשימה. ההפרש בין שתי אבנים יכול להיות קל יותר מאבנים שעדיין לא נגעת בהן, ולכן סדר קבוע מתיישן אחרי הסיבוב הראשון.

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

מהי סיבוכיות הזמן של Last Stone Weight?

בעזרת ערימת מקסימום, בניית הערימה ומשחק של לכל היותר n-1 סבבים, שבכל אחד מהם מבצעים שתי שליפות והכנסה אחת, אורכים O(n log n) זמן ודורשים O(n) מקום. מיון כל הערימה בכל סבב במקום זאת אורך O(n² log n).

למה להשתמש בערימת מינימום עבור Last Stone Weight?

בכל סיבוב מבקשים את שני הערכים הגדולים ביותר באוסף שמשתנה אחרי כל סיבוב. ערימת מקסימום עונה על השאלה "מהו הערך הגדול ביותר" ומקבלת ערך חדש בזמן O(log n), בלי לשמור את כל האוסף ממוין. זה בדיוק מה שהסימולציה חוזרת עליו.

האם אפשר לפתור את בעיית Last Stone Weight בלי ערימה?

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

האם סדר ניפוץ המשקולות השוות משנה את התשובה?

לא. כאשר כמה אבנים חולקות את המשקל הכבד ביותר, שתי האבנים שתבחרו שוקלות אותו דבר בכל מקרה, ולכן הערימה לאחר הסיבוב מכילה את אותם משקלים. התשובה תלויה רק במשקלים, ולכן כל פתרון נכון מחזיר את אותו מספר.

Python

def lastStoneWeight(stones):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

stones = [3, 9, 4, 6, 2]

צפוי