Jump Game

Q: למה הגישה החמדנית עובדת במשחק הקפיצות?

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

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

+10

אתה עומד באינדקס 0 של המערך nums. מהאינדקס i אפשר לקפוץ קדימה מספר צעדים כלשהו בין 1 ל־nums[i], כך ש־nums[i] הוא הקפיצה הארוכה ביותר שלך משם, ו־0 פירושו שאינך יכול לזוז. החזר true אם רצף כלשהו של קפיצות מגיע לאינדקס האחרון, ואחרת החזר false.

פונקציה

canJump(nums: integer-array) → boolean

numsinteger-array: הקפיצה הארוכה ביותר שאפשר לבצע מכל אינדקס
מחזירהboolean: אמת אם אפשר להגיע לאינדקס האחרון החל מאינדקס 0, אחרת שקר

אילוצים

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵
קפיצה עשויה להיות קצרה מ־nums[i], ולכן קפיצה ארוכה לעולם לא תאלץ אותך לעבור את האינדקס האחרון.

דוגמאות

קלט: nums = [2, 0, 3, 1, 0, 2]
פלט: true
הסבר: ממפתח 0 אפשר להגיע למפתח 1 או 2. במפתח 1 נמצא 0 והוא מבוי סתום, אבל במפתח 2 נמצא 3 ואפשר להגיע ממנו למפתח 5, המפתח האחרון.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

נסו כל קפיצה

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

האינטואיציה

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

בדוגמה הראשונה, הערך באינדקס 0 הוא 2, ולכן מנסים את אינדקס 1 ואת אינדקס 2. הערך באינדקס 1 הוא 0, וזהו מבוי סתום, ולכן חוזרים לאחור ומנסים את אינדקס 2. הערך באינדקס 2 הוא 3, והוא מגיע לאינדקס 5, האינדקס האחרון, והחיפוש מסתיים בתוצאה true.

החיפוש נכון כי הוא בודק כל מסלול. זו גם הבעיה שלו: הוא אף פעם לא זוכר אינדקס שכבר בדק, ולכן בודק שוב את אותו אינדקס עבור כל מסלול שמגיע אליו. כשהתשובה היא false, הוא חייב לשלול כל מסלול. בתוך [4, 3, 2, 1, 0, 5] כל אינדקס לפני ה-0 יכול להגיע ל-0, ולכן יש 8 מסלולים שונים שמגיעים אליו. עם 30 אינדקסים כאלה יש יותר מ-500 מיליון מסלולים, ובבדיקות הגדולות ביותר יש 10,000 איברים. מסלול ארוך כל כך גם גורם לגלישת מחסנית הקריאות בשפות מסוימות: Python נעצרת כברירת מחדל אחרי 1,000 קריאות מקוננות.

אלגוריתם

כתבו פונקציית עזר reach(i) שעונה על השאלה: האם אפשר להגיע מהאינדקס i לאינדקס האחרון?
אם i הוא האינדקס האחרון, החזירו true.
אחרת, נסו כל נקודת נחיתה next מ־i+1 עד min(i+nums[i], n-1), והחזירו true ברגע ש־reach(next) מחזירה זאת.
אם אף נקודת נחיתה לא מצליחה, החזירו false.
התשובה היא reach(0).

def canJump(nums):
    last = len(nums) - 1

    def reach(i):
        # Can you get from index i to the last index?
        if i == last:
            return True
        for nxt in range(i + 1, min(i + nums[i], last) + 1):
            if reach(nxt):
                return True
        return False

    return reach(0)

זכור אילו אינדקסים יכולים להסתיים

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

האינטואיציה

החיפוש שלמעלה שואל שוב ושוב את אותה שאלה: "האם אפשר להגיע לסוף החל מאינדקס j?" התשובה עבור j לעולם לא משתנה, לכן חשבו אותה פעם אחת ושמרו אותה. נקרא לאינדקס טוב אם אפשר להגיע ממנו לאינדקס האחרון. האינדקס האחרון הוא טוב. כל אינדקס אחר i הוא טוב אם לפחות אחד מהאינדקסים שאליהם אפשר להגיע ממנו, מ-i+1 עד i+nums[i], הוא טוב.

כל אינדקס תלוי רק באינדקסים שמימינו, לכן מלאו את הטבלה good מימין לשמאל. בדוגמה הראשונה, אינדקס 5 הוא טוב. הערך באינדקס 4 הוא 0, לכן הוא אינו טוב. מאינדקס 3 אפשר להגיע רק לאינדקס 4: הוא אינו טוב. מאינדקס 2 אפשר להגיע לאינדקסים 3, 4 ו-5, ואינדקס 5 הוא טוב, לכן 2 הוא טוב. הערך באינדקס 1 הוא 0: הוא אינו טוב. מאינדקס 0 אפשר להגיע לאינדקסים 1 ו-2, ואינדקס 2 הוא טוב, לכן התשובה היא true.

כעת ההחלטה לגבי כל אינדקס מתקבלת פעם אחת, אבל כדי לקבל אותה עדיין עשויים לסרוק עד n תאים. ב-[9998, 9997, …, 1, 0, 7] כל אינדקס יכול להגיע ל-0 ולא לשום דבר מעבר לו, ולכן כל אחד מהם סורק את כל הטווח שלו ולא מוצא שום אינדקס טוב. מדובר בכ-5 × 10^7 בדיקות עבור 10,000 איברים, והבדיקות הגדולות ביותר בנויות כך. כמות העבודה גדלה כריבוע האורך, ולכן התוכנית לא מספיקה לסיים בזמן.

אלגוריתם

צרו מערך בוליאני good באורך n והגדירו את good[n-1] כ-true.
עברו על i מ-n-2 ועד 0.
סרקו את j מ-i+1 ועד min(i+nums[i], n-1). אם אחד מערכי good[j] הוא true, הגדירו את good[i] כ-true והפסיקו לסרוק.
החזירו את good[0].

def canJump(nums):
    n = len(nums)
    good = [False] * n  # good[i]: from i you can reach the last index
    good[n - 1] = True
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, min(i + nums[i], n - 1) + 1):
            if good[j]:
                good[i] = True
                break
    return good[0]

מעקב אחר האינדקס הרחוק ביותר שניתן להגיע אליו

האינטואיציה

בדוק לאילו אינדקסים אפשר להגיע, ולא את המסלולים. מאינדקס i אפשר לנחות בכל אינדקס מ־i+1 ועד i+nums[i], בלי פערים. לכן, ברגע שאפשר להגיע לאינדקס i, אפשר להגיע גם לכל אינדקס עד i+nums[i]. התחל רק עם אינדקס 0 והמשך להוסיף את הטווחים האלה. כל טווח חדש מתחיל בתוך הבלוק שכבר יש לך, ולכן האינדקסים שאפשר להגיע אליהם תמיד יוצרים בלוק אחד רציף, [0, farthest].

לכן מספיק מספר אחד. עבור על i משמאל לימין. כל עוד i ≤ farthest, אפשר להגיע לאינדקס i, ולכן הרחב את farthest ל־max(farthest, i+nums[i]). אם i אי פעם עובר את farthest, אף אינדקס שאפשר להגיע אליו לא מזנק אל i. הבלוק לא יכול לגדול מעבר לפער הזה, ולכן אי אפשר להגיע לשום אינדקס שמימינו, כולל האינדקס האחרון. אם המעבר מגיע לסוף בלי פער, אפשר להגיע לאינדקס האחרון.

בדוגמה השנייה, farthest הוא 0, ואז 1 אחרי אינדקס 0, ואז 4 אחרי אינדקס 1. באינדקסים 2, 3 ו־4 יש 0, והערך נשאר 4. אינדקס 5 נמצא מעבר ל־4, ולכן התשובה היא false. בדוגמה הראשונה, אינדקס 2 דוחף את farthest ל־5, ואף אינדקס אינו עובר אותו, ולכן התשובה היא true.

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

אלגוריתם

הגדר את farthest = 0.
עבור כל אינדקס i משמאל לימין: אם i > farthest, החזר false.
אחרת הגדר את farthest = max(farthest, i+nums[i]).
אם הלולאה מסתיימת, ניתן היה להגיע לכל האינדקסים, לכן החזר true.

def canJump(nums):
    farthest = 0  # every index up to farthest can be reached
    for i, jump in enumerate(nums):
        if i > farthest:
            return False  # nothing reachable jumps to i
        farthest = max(farthest, i + jump)
    return True

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

רוב התשובות השגויות נובעות מקריאת nums[i] כאילו הוא הקפיצה היחידה, או מסדר שתי הבדיקות בתוך הלולאה.

תמיד לקפוץ בדיוק nums[i] צעדים, או תמיד לבחור בקפיצה הארוכה ביותר. עם [2, 5, 0, 0] הקפיצה המלאה מהאינדקס 0 נוחתת על 0, בעוד שקפיצה של צעד אחד לאינדקס 1 מגיעה לסוף.
להחזיר false ברגע שרואים 0. ל-0 יש חשיבות רק אם שום דבר שלפניו לא קופץ מעליו: [2, 0, 1] קופץ מעל ה-0 והתשובה היא true.
לעדכן את farthest לפני שבודקים i > farthest. אינדקס שאי אפשר להגיע אליו לא אמור להאריך את הטווח, לכן קודם בודקים ורק אחר כך מעדכנים.
להתייחס למערך בעל איבר אחד כאל כישלון. את כבר עומדת על האינדקס האחרון, לכן התשובה היא true, גם כשהאיבר הזה הוא 0.
לבצע קריאה רקורסיבית עבור מערכים ארוכים. מסלול יכול להיות באורך 10,000 קפיצות, מה שגורם לגלישת מחסנית הקריאות בכמה שפות. במעבר יחיד אין שימוש ברקורסיה.

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

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

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

למה הגישה החמדנית עובדת במשחק הקפיצות?

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

האם משחק הקפיצה הוא בעיית תכנות דינמי?

אפשר לפתור זאת באמצעות תכנות דינמי: מסמנים כל אינדקס כטוב אם אחד ממקומות הנחיתה שלו טוב, וממלאים את הטבלה מימין לשמאל. הסיבוכיות היא O(n²). שימו לב שרק האינדקס הטוב השמאלי ביותר חשוב, מכיוון שכל אינדקס שמגיע לאינדקס טוב מגיע גם אליו. שומרים רק את האינדקס הזה, goal, ומעבירים אותו ל-i בכל פעם ש-i+nums[i] ≥ goal. התשובה היא האם goal מגיע בסוף ל-0 — מעבר של O(n) שמשקף את המעבר החמדני.

איך מוצאים את המספר המינימלי של קפיצות?

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

Python

def canJump(nums):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [2, 0, 3, 1, 0, 2]

צפוי

true

Jump Game

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו כל קפיצה

זכור אילו אינדקסים יכולים להסתיים

מעקב אחר האינדקס הרחוק ביותר שניתן להגיע אליו

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

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

בעיות דומות