題目描述

LC 題 - 55
給定一個非負整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標 。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標。

示例 1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。

示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標。

題解

思路1:動態(tài)規(guī)劃

核心點在于數(shù)組中元素為0時能否跳過

令dp[i] 表示i此時可以跳的最大步長，當遍歷到某個i，dp[i]<=0時，說明無法再向前，則返回false

dp[i]的動態(tài)轉(zhuǎn)移方程：dp[i] = max(nums[i],dp[i-1]-1),即當前位置i的步長和上一個位置i-1的最大步長-1兩者的最大值
邊界條件dp[0] = nums[0]

// OC
+ (BOOL)canJump1:(NSArray *)nums {
    int n = (int)nums.count;
    if (n == 0) {
        return NO;
    }
    int dp[n];
    dp[0] = [nums[0] intValue];
    if (dp[0] <= 0) {
        return n==1;
    }
    
    for (int i=1; i<n; i++) {
        dp[i] = MAX([nums[i] intValue], dp[i-1]-1);
        if (dp[i] <= 0 && i<n-1) {
            return NO;
        }
    }
    return YES;
    
}

// Swift
    static public func canJump1(_ nums:[Int]) -> Bool {
        let n = nums.count
        if n == 0 {return false}
        var dp = Array(repeating: 0, count: n)
        dp[0] = nums[0]
        if dp[0] <= 0 {
            return n==1
        }
        
        for i in 1..<n {
            dp[i] = max(dp[i-1]-1, nums[i])
            if dp[i] <= 0 && i<n-1 {
                return false
            }
        }
        return true
    }

思路2:貪心

對于任意位置i，它所能到達的最遠位置為maxRight = i + nums[i]，也就是說 對于每一個可以到達的位置x，它使得 x+1,x+2,?,x+nums[x] 這些連續(xù)的位置都可以到達。

我們依次遍歷數(shù)組中的每一個位置，并實時維護能到達的最遠位置maxRight,如果當前遍歷的位置i<=maxRight(也就是說當前位置i可以到達)，那么我們用max(maxRight,i+nums[i])來更新最遠到達位置maxRight，在遍歷過程中，如果maxRight>=y(y為指定位置)，則表示y位置可以到達，返回true。如果直到遍歷結(jié)束都沒有maxRight>=y，則返回false

// OC
+ (BOOL)canJump2:(NSArray *)nums {
    int n = (int)nums.count;
    if (n == 0) {
        return NO;
    }
    int maxRight = 0;
    for (int i=0; i<n; i++) {
        if (i<=maxRight) {
            maxRight = MAX([nums[i] intValue]+i, maxRight);
            if (maxRight >= n-1) {
                return YES;
            }
        }
    }
    return NO;
}

// Swift
    static public func canJump2(_ nums:[Int]) -> Bool {
        let n = nums.count
        if n == 0 {return false}
        var maxRight = 0
        for i in 0..<n {
            if i <= maxRight {
                maxRight = max(maxRight, i+nums[i])
                if maxRight >= n-1 {
                    return true
                }
            }
        }
        return false
    }

思路3: 逆向遍歷

如果位置i可以到達終點k點，那么逆序時k點也是可以回到i點的

令初始終點end=n-1，逆序遍歷i，i從n-2到0，如果nums[i]+i>=end，則更新終點end=i，遍歷結(jié)束判斷終點是否為0，為0則返回true ，否則false

假設(shè)位置i,j(i<j)都可以到達終點end=k(i<j<k，nums[i]+i>=k，nums[j]+j>=k)，逆序遍歷時，先遍歷到j(luò)，由于nums[j]+j>=k，即從j位置可以到達k點，更新終點end=j，再遍歷到i時，由于nums[i]+i>=k>j，即從i位置可以到達j，更新終點end=i。也就是說如果i點可以到達終點end，那么從終點也可以回到初始位置i

// OC
+ (BOOL)canJump3:(NSArray *)nums {
    int n = (int)nums.count;
    if (n == 0) {
        return NO;
    }
    int end = n-1;
    for (int i=end-1; i>=0; i--) {
        if ([nums[i] intValue] + i >= end) {
            end = i;
        }
    }
    return end == 0;
}

// Swift
    static public func canJump3(_ nums:[Int]) -> Bool {
        let n = nums.count
        if n == 0 {return false}
        var end = n-1
        var i = n-2
        while i>=0 {
            if nums[i] + i >= end {
                // 更新終點
                end = i
            }
            i -= 1
        }
        return end==0
    }

參考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvb8zs/

https://leetcode-cn.com/problems/jump-game/solution/tiao-yue-you-xi-by-leetcode-solution/