Baseball Game

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

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

Q: איך מבדילים בין מספר לפעולה במשחק הבייסבול?

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

קלמחסנית

+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.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

האינטואיציה

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

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

כשהפעולות מסתיימות, הרשימה מכילה בדיוק את הניקודים שנספרים. חברו אותם. כל פעולה היא O(1) והסכום הסופי הוא O(n), לכן זמן הריצה הכולל הוא 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 ששווה תמיד לסכום המחסנית. כל הוספה דוחפת את הניקוד החדש אל total, וכל "C" מפחית ממנו את הניקוד שהוא מוציא מהמחסנית.

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

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

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

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

שמירה רק על סכום מצטבר ועל שני הניקודים האחרונים. אחרי "C", צריך את הניקוד שקדם לשני אלה, ולכן ביטול ואחריו "+" יקרא ערכים מיושנים. יש לשמור את כל המחסנית.
שוכחים שניקודים שבוטלו יוצאים מהסכום. כשמשתמשים בסכום מצטבר, "C" חייב להפחית את הניקוד שנשלף, ולא להתעלם ממנו.
פענוח ניקודים שליליים ידנית והשמטת סימן המינוס. יש להשתמש במנתח המספרים השלמים של השפה, שקורא את "-2" בתור -2.
בדיקה אם יש ספרה כדי להחליט אם רשומה היא מספר. "-5" מתחיל בסימן מינוס; יש לבדוק את שלושת הסימנים ולטפל בכל השאר כמספר.
הנחה שהתשובה חיובית. ניקודים שליליים וביטולים יכולים להוביל לסכום שלילי, או ל־0 כשכל הניקודים בוטלו.

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

מהי סיבוכיות הזמן של Baseball Game?

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

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

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

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

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

איך מבדילים בין מספר לפעולה במשחק הבייסבול?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

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

צפוי