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 הוא התשובה.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

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

האינטואיציה

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

בכל סיבוב מוסרת לפחות אבן אחת, ולכן יש עד n-1 סיבובים, ובכל אחד ממיינים עד n אבנים: O(n² log n). עבור n = 10^4 מדובר בכ-10^4 פעולות מיון של עד 10^4 מספרים.

אלגוריתם

העתיקו את האבנים לרשימה בשם 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.

יש לכל היותר n-1 סבבים של שתי שליפות והכנסה אחת, לכן זמן הריצה הוא O(n log n) והזיכרון הוא O(n). בשפות שאין בהן ערימה מובנית, הפתרון מחזיק את הערימה במערך, כשההורה של האינדקס 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 מחזירים את הערך הקטן ביותר; יש להפוך את סימני המשקלים או להעביר משווה הפוך.
שכחת הסימן כשמשתמשים במשקלים שליליים. שני הערכים שהוצאו הם שליליים, ולכן הערך שיש להכניס הוא -(heaviest - second).
מיון פעם אחת בתחילת הדרך ומעבר על הרשימה. ההפרש יכול להיות קטן מאבנים שעדיין לא נגעת בהן, ולכן הסדר מתיישן כבר אחרי הסיבוב הראשון.

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

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

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

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

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

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

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

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

הפלט הצפוי