Remove K Digits

Q: מהי סיבוכיות הזמן של Remove K Digits?

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

בינונימחסנית מונוטונית אלגוריתם חמדן

+10

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

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

פונקציה

removeKdigits(num: string, k: integer) → string

numstring: המספר, הכתוב כמחרוזת של ספרות
kinteger: כמה ספרות להסיר
מחזירהstring: המספר הקטן ביותר שאפשר להשאיר כמחרוזת ללא אפסים מובילים

אילוצים

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num מכיל רק את הספרות 0 עד 9.
ל־num אין אפסים מובילים, למעט כשהוא המספר אפס עצמו, "0".

דוגמאות

קלט: num = "4325043"k = 3
פלט: "2043"
הסבר: הסרת ה־4 וה־3 הראשון מציבה את ה־2 בהתחלה. ה־0 לא יכול להיות ראשון: ארבע ספרות עומדות לפניו ויש לך שלוש הסרות. ההסרה האחרונה לוקחת את ה־5, שנמצא לפני 0 קטן ממנו.

קלט: num = "30200"k = 1
פלט: "200"
הסבר: הסרת הספרה 3 משאירה את 0200, וללא האפס המוביל שלה זה 200. כל הסרה אחרת משאירה את הספרה 3 בהתחלה ומשאירה מספר בן ארבע ספרות, כגון 3000.

קלט: num = "52"k = 2
פלט: "0"
הסבר: שתי הספרות מוסרות, ולכן לא נשאר כלום והתשובה היא "0".

שאלת המשך

איך תשנה את הפתרון כדי להסיר k ספרות ולהשאיר במקום זאת את המספר הגדול ביותר?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

הסר ספרה אחת בכל פעם

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

האינטואיציה

הסר ספרה אחת בכל פעם: מצא את המיקום הראשון i שבו num[i] > num[i+1] ומחק את num[i], או מחק את הספרה האחרונה אם הספרות אף פעם לא יורדות. חזור על כך k פעמים.

בכל תשובה נשארות n-k ספרות, ולכן המיקום הראשון שבו שתי תשובות שונות קובע איזו מהן קטנה יותר. עד i הספרות אף פעם לא יורדות, ולכן מחיקת ספרה מוקדמת יותר מכניסה במקומה ספרה גדולה ממנה או שווה לה; מחיקת ספרה מאוחרת יותר משאירה את num[i] הגדולה במקומה. מחיקת num[i] מקטינה את הספרה המוקדמת ביותר שאפשר להקטין.

כל מחיקה סורקת מחדש משמאל ומזיזה את הספרות שאחריה, ולכן זמן הריצה הוא O(n·k). עבור 40,000 ספרות 1 עם k = 25,000, הסריקות קוראות כ־6.9 × 10^8 ספרות.

אלגוריתם

העתק את הספרות לרשימה שתוכל למחוק ממנה.
חזור על הפעולה k פעמים: עבור משמאל עד לספרה הראשונה שגדולה מהספרה שאחריה, או עד לספרה האחרונה, ומחק אותה.
הסר את האפסים המובילים, והחזר "0" אם לא נשאר דבר.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

מחסנית מונוטונית של ספרות שנשמרו

האינטואיציה

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

במקרה של 4325043 עם k = 3, הספרה 3 גורמת להוצאת 4, הספרה 2 גורמת להוצאת 3, והספרה 0 גורמת להוצאת 5. הספרות 4 ו־3 נדחפות למחסנית כשהן מגיעות, והתוצאה היא 2043.

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

אלגוריתם

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

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

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

הסרה כאשר הספרה העליונה שווה לספרה החדשה. ב־112 עם k = 1, נשאר 12; התשובה הנכונה היא 11.
שוכחים את ההסרות שנותרו אחרי הלולאה, או מבצעים אותן מההתחלה. המחסנית אף פעם לא קטנה, ולכן הספרות האחרונות שלה הן: 123456789 עם k = 3 נותן 123456.
סופרים אפסים שהוסרו כהסרות. ב־100200 עם k = 1, הספרה 1 היא ההסרה היחידה; האפסים שבהתחלה מוסרים בחינם, והתשובה היא 200.
מחזירים מחרוזת ריקה. ב־10 עם k = 1 נשאר רק אפס, ולכן התשובה היא "0".
ממירים את num למספר שלם. יכולים להיות בו 4 × 10^4 ספרות, הרבה מעבר לכל טיפוס מספר שלם, לכן יש להשוות את הספרות כתווים.

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

מהי סיבוכיות הזמן של Remove K Digits?

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

איך מטפלים באפסים מובילים ב-Remove K Digits?

קודם הסר את הספרות, והסר את האפסים רק בסוף. אפס בתחילת המספר לא משנה את הערך, ולכן הסרתו אינה עולה דבר: 10200 כאשר k = 1 הופך ל-0200 ואז ל-200. אם לאחר הסרת האפסים לא נשאר דבר, החזר "0".

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

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

def removeKdigits(num, k):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

num = "4325043"
k = 3

הפלט הצפוי

"2043"