Baseball Game

Q: מהי סיבוכיות הזמן של משחק בייסבול?

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

Q: האם אפשר לפתור את משחק הבייסבול עם מקום נוסף בסיבוכיות O(1)?

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

קלמחסנית

+10

אתם מנהלים ניקוד במשחק יוצא דופן. קראו את operations משמאל לימין; כל ערך משנה את רישום הניקוד. מספר שלם כמו "7" או "-2" מוסיף את הניקוד הזה. "+" מוסיף את סכום שני הניקודים האחרונים, "D" מוסיף פי שניים מהניקוד האחרון, ו-"C" מסיר את הניקוד האחרון לצמיתות.

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

פונקציה

calPoints(operations: string-array) → integer

operationsstring-array: הפעולות לפי הסדר: מספרים שלמים כטקסט, או "+", "D", "C"
מחזירהinteger: סכום הנקודות שעדיין רשומות בסוף

אילוצים

1 ≤ operations.length ≤ 5000
כל ערך הוא "+",‏ "D",‏ "C", או מספר שלם הכתוב בשיטה העשרונית, כך ש־-3 × 10⁴ ≤ value ≤ 3 × 10⁴.
כל פעולה תקפה: "+" מופיע רק כאשר הרשומה מכילה לפחות שתי תוצאות, ו-"D" ו-"C" רק כאשר היא מכילה לפחות תוצאה אחת.
כל ניקוד ברשומה והסכום הסופי נכנסים למספר שלם חתום בן 32 סיביות.

דוגמאות

קלט: operations = ["4", "-2", "D", "+", "C", "7"]
פלט: 5
הסבר: הרשומה גדלה ל־[4, -2],‏ "D" מוסיף -4,‏ "+" מוסיף -2 + -4 = -6,‏ "C" מסיר את -6, ו־7 נוסף אחרון. סכום הרשומה [4, -2, -4, 7] הוא 5.

קלט: operations = ["6", "D", "C", "C"]
פלט: 0
הסבר: "D" מוסיף 12 אחרי 6, ואז שתי הרשומות "C" מסירות את 12 ואת 6. לא נשאר כלום, ולכן התשובה היא 0.

קלט: operations = ["1", "2", "+", "+", "D"]
פלט: 21
הסבר: שתי הרשומות "+" מחברות את 1 + 2 = 3 ואז את 2 + 3 = 5, ו-"D" מוסיף 10. הרשומה [1, 2, 3, 5, 10] מסתכמת ב-21.

שאלת המשך

איך היית מוסיף פעולה שמבטלת את "C" האחרון, ומחזירה את הניקוד שבוטל, בזמן O(1)?

רמזים

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

נפתחו 0 מתוך 3

פתרון

כל פעולה קוראת את הניקוד העדכני ביותר, ו־"C" יכולה להסיר אותם אחד בכל פעם, כך שניקוד ישן יותר הופך שוב לעדכני ביותר. זהו עקרון אחרון נכנס, ראשון יוצא: דוחפים כל ניקוד חדש, מוציאים ניקוד בעת "C", וקוראים את הניקוד העליון או את שני הניקודים העליונים עבור "D" ו־"+".

בנה את הרשומה במחסנית, חבר את הערכים בסוף

האינטואיציה

שמרו את הרשומות כרשימה, כשהניקוד החדש ביותר נמצא בסוף, כך שכל פעולה נוגעת רק בסוף. אחרי "C" הניקוד השני החדש ביותר הופך לחדש ביותר, ופעולה מאוחרת יותר של "D" או "+" חייבת לקרוא אותו; הוצאה מהרשימה חושפת אותו. בדוגמה הראשונה "C" מוציא את -6 ומשאיר את [4, -2, -4].

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

אלגוריתם

התחל עם מחסנית ריקה record.
עבור "+", דחוף את הסכום של שתי הרשומות העליונות. עבור "D", דחוף פי שניים מהרשומה העליונה.
עבור "C", הוצא את הרשומה העליונה.
אחרת, הרשומה היא מספר: המר את הטקסט למספר שלם ודחוף אותו.
החזר את הסכום של כל מה שנותר במחסנית.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    for op in operations:
        if op == "+":
            record.append(record[-1] + record[-2])
        elif op == "D":
            record.append(2 * record[-1])
        elif op == "C":
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

מחסנית עם סכום מצטבר

האינטואיציה

שמור על total שווה לסכום המחסנית: כל דחיפה מוסיפה את הניקוד החדש, וכל "C" מחסירה את הניקוד שהיא מוציאה מהמחסנית. המחסנית חייבת להישאר, כי פעולת ביטול צריכה לדעת איזה ניקוד להסיר. בדוגמה הראשונה הסכום משתנה ל־4, 2, -2, -8, פעולת הביטול מסירה בחזרה את -6 ומביאה אותו ל־-2, ו־7 מביא אותו ל־5.

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

אלגוריתם

התחל עם מחסנית ריקה record ועם total = 0.
עבור "C", הוצא את הניקוד שבראש המחסנית והחסר אותו מ־total.
אחרת, חשב את הניקוד החדש: סכום שני הניקודים שבראש המחסנית עבור "+", פי שניים מהניקוד שבראש המחסנית עבור "D", או המספר השלם עצמו.
דחוף את הניקוד החדש למחסנית והוסף אותו ל־total.
החזר את total.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    total = 0    # always the sum of record
    for op in operations:
        if op == "C":
            total -= record.pop()  # the cancelled score leaves the total too
            continue
        if op == "+":
            score = record[-1] + record[-2]
        elif op == "D":
            score = 2 * record[-1]
        else:
            score = int(op)
        record.append(score)
        total += score
    return total

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

שמירה של סכום מצטבר בלבד ושל שתי התוצאות האחרונות. ב־["1", "2", "3", "C", "+"] הפעולה "+" צריכה את 1 ואת 2, ובחלון של שתי תוצאות כבר אין את 1.
אי־הפחתת תוצאה שבוטלה מהסכום המצטבר. בדוגמה השנייה, כך מתקבל 18 במקום 0.
החלטה שערך הוא מספר על סמך בדיקה אם יש בו ספרה. "-2" מתחיל בסימן מינוס; השוו לשלושת הסמלים, ונתחו את כל השאר באמצעות מנתח המספרים השלמים של השפה.
הנחה שהתשובה חיובית. הסכום של ["-3", "D"] הוא -9.

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

מהי סיבוכיות הזמן של משחק בייסבול?

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

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

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

האם אפשר לפתור את משחק הבייסבול עם מקום נוסף בסיבוכיות O(1)?

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

def calPoints(operations):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

operations = ["4", "-2", "D", "+", "C", "7"]

הפלט הצפוי