leetcode 55 Jump Game || 45 Jump Game II

本次题解包括

• 45. Jump Game II
• 55. Jump Game

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example: A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

题目地址：leetcode Jump Game

题目大意: 数组nums[i]表示能i这个位置能调到的步数。判断是否能从0跳到n-1

思路:

一看，不用构图，隐式的BFS，一敲TLE

想想DP O(N)过了,设maxJump为当前最远能跳到的距离。如果i+maxJump>=n-1说明true，若maxJump=0说明没办法跳了，为false

设maxJump为跳到的最远距离，每i++，那么maxJump--。 然后判断是否可以更新maxJump。如果中途maxJump=0，显然无解。

C++

class Solution {
public:
	bool canJump(int A[], int n) {
		if (n == 1) return true;
		int maxJump =0;//current you can jump
		for (int i = 0; i < n; i++){
			maxJump--;
			if (maxJump < A[i])
				maxJump = A[i];
			
			if (!maxJump)
				return false;

			if (maxJump + i >= n - 1 )
				return true;
		}
		return false;
	}
};

 

更简单的写法：

cover表示当前覆盖到的下标，

• cover < i 则无解
• 如果cover >= len(nums)-1，说明跳到了目的地，有解。
• 否则cover = max(cover, nums[i] + i) 即更新最大的跳到的位置

C++

class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
        for(int i = 0; i < nums.size(); ++i){
            if(cover < i) return false;
            cover = max(cover, nums[i] + i);
            if(cover >= nums.size() - 1)
                return true;
        }
        return false;
}
};

Python

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        cover = 0
        for i in range(len(nums)):
            if cover < i: return False
            cover = max(cover,nums[i] + i)
            if cover >= len(nums) - 1:
                return True
        return False

另一种写法：

维护l,r为当前的区间（类似BFS的思想），然后每次在这区间中取能跳到的最远距离。每次更新l =  r + 1, r = new_r

若最终r比n-1大，说明可以到达。复杂度也是O(n)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = 0;
        while(l <= r && r < n - 1){
            int nr = r;
            for(int i = l; i <= r; ++i)
                nr = max(nr, i + nums[i]);
            l = r + 1;
            r = nr;
        }
        return r >= n - 1;
    }
};

 

---

45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note: You can assume that you can always reach the last index.

题目地址：leetcode Jump Game II

题目大意: 和55题差不多，只不过是求到终点的最小步数。

思路:

DP超时，可以用类似55题的方法：

cur_cover表示当前能跳到的最远距离，last_cover表示上次最远可以跳到的距离。

那么，对于每次last_cover < i 时，说明跳上一次不到i，需要++level

C++

class Solution {
public:
int jump(vector<int>& nums) {
int level = 0, last_cover = 0, cur_cover = 0;
        for(int i = 0; i < nums.size(); ++i){
            if(last_cover < i){
                last_cover = cur_cover;
                ++level;
            }
            else if(last_cover >= nums.size() - 1)
                return level;
            cur_cover = max(cur_cover, nums[i] + i);
        }
return level;
}
};

Python

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        level = last_cover = cur_cover = 0
        for i in range(len(nums)):
            if last_cover < i:
                last_cover = cur_cover
                level += 1
            elif last_cover >= len(nums) - 1:
                return level
            cur_cover = max(cur_cover, nums[i] + i)
        return level

另一种写法：

维护l,r为当前的区间（类似BFS的思想），然后每次在这区间中取能跳到的最远距离，这区间的step都是相同的。

若最终r比n-1大，说明可以到达，且step步。复杂度也是O(n)

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = 0, step = 0;
        while(r < n - 1){
            int nr = r;
            for(int i = l; i <= r; ++i)
                nr = max(nr, i + nums[i]);
            ++step;
            l = r + 1;
            r = nr;
        }
        return step;
    }
};

 

本文是leetcode如下的题解

• 45. Jump Game II
• 55. Jump Game

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/