Leetcode-55 Jump Game

发表于 | 分类于 | 次

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.

Example 1

1
2
3
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2

1
2
3
4
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

解题思路

  1. 法一。首先想到动态规划。能否从位置 i 到达末尾，取决于能否从位置 i+1 至 i+nums[i] 到达末尾，因此需要从后往前确定每个位置能否到达末尾并记录之。
  2. 法二。如果某个位置能够到达末尾，那么在该位置之前，只需要能够到达该位置即可。因此，可以将目标位置往前移动，使其靠近起点。若目标位置与起点重合，输出为真；否则输出为假。

复杂度分析

  1. 法一。

    时间复杂度：$O(n^2)$

    空间复杂度：$O(n)$

  2. 法二。

    时间复杂度：$O(n)$

    空间复杂度：$O(1)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution1 {
public:
	bool canJump(vector<int>& nums) {
		int n = nums.size();
		vector<bool> can(n, false);
		can[n - 1] = true;
		for (int i = n - 2; i >= 0; i--) {
			int maxr = min(nums[i] + i, n - 1); //防止越界
			//遍历所达范围内是否有位置能够到达数组末尾
			for (int j = i + 1; j <= maxr; ++j) {
				if (can[j]) {
					can[i] = true;
					break;
				}
			}
		}
		return can[0];
	}
};

class Solution2 {
public:
	bool canJump(vector<int>& nums) {
		int lastPos = nums.size() - 1;
		for (int i = lastPos - 1; i >= 0; i--) {
			if (i + nums[i] >= lastPos) lastPos = i;
		}
		return lastPos == 0;
	}
};