55. 跳跃游戏
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
class Solution {
public:
int isUsed[30000] = {0};
//思路：回溯 + 贪心
//回溯三部曲
//1.确定返回类型和参数
bool backtracing(vector<int>& nums, int startIndex)
{
//2.终止条件
//如果这个到达这个位置后可以到达最后的位置
if(startIndex >= nums.size() - 1 ) return true;
//如果该位置可移动距离为0 或者该位置曾经走过（又走一遍说明上一次走到这个位置后再往前怎么走都走不通了）
else if(nums[startIndex] == 0 || isUsed[startIndex]) return false;
//如果这个位置可以开始走了，那么先把这个位置设置为走过了
isUsed[startIndex] = 1;
//3.每次回溯的遍历过程
for(int i = nums[startIndex]; i > 0; i--)
{
//如果从这个位置起步走发现能走到终点那么就会一步一步地往上返回true
if(backtracing(nums, startIndex + i)) return true;
}
//遍历完了也没有找到
return false;
}
bool canJump(vector<int>& nums) {
return backtracing(nums, 0);
}
};
这是我的思路，回溯，到一个位置后先往远了跳，不行就减1，而且每次走过的位置标记一下，再次跑到同样位置就直接终止。
过是过了，就是时间和空间用的很多，岂可休！
本来想改成动态生成数组，结果leetcode老是说我数组越界，明明VS上跑的非常正确，查了之后发现leetcode编译会先判断会不会越界，麻了。
但在创建动态数组的时候，得这么写，不乘num.size()的话，就只有a[0]被初始化为0了。
1
2
3
int* a;
a = new int[num.size()];
memset(a, 0, sizeof(a) * num.size());
如果不是动态数组，初始就创建了个a[5]，这么写就没问题了：
1
2
int a[5];
memset(a, 0, sizeof(a));
代码随想录的思路是贪心：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
//判断当前位置能覆盖的最大位置是否能够到达最后一个下标
bool canJump(vector<int>& nums) {
int cover = 0;//初始覆盖的范围为0
//如果只有一个数，那么开始就已经到了
if(nums.size() == 1) return true;
//注意，要 <= cover cover是到当前位置能覆盖的最远位置，也就是说一定能走到的下标是cover
for(int i = 0; i <= cover; i++)
{
//更新能覆盖的最远下标值
cover = max(i + nums[i], cover);
//如果最远下标已经到达最后一个
if(cover >= nums.size() - 1) return true;
}
return false;
}
};
节省了不少时间和空间，但能想到这个方法还是挺难的~
45. 跳跃游戏 II
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
class Solution {
public:
int cnt = 0;
void cal(vector<int>& nums, int maxIndex)
{
if(maxIndex == 0) return;
int cover = 0;
for(int i = 0; i <= cover; i++)
{
cover = max(cover, i + nums[i]);
if(cover >= maxIndex)
{
cnt++;
//去找到能走到i这个位置的最小下标
cal(nums, i);
return;
}
}
}
int jump(vector<int>& nums) {
cal(nums, nums.size() - 1);
return cnt;
}
};
我的思路借助了上一个贪心的方法，通过递归，利用贪心算法不断从头开始找能到达终点的最小位置，这里的终点是在不断地变化的，一开始是素组的最后一个下标，递归一次后终点就成了能到达终点的最小下标，直到终点为0时，结束递归。
战绩不佳，时间和空间都只战胜了20%。
代码随想录的思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() == 1) return 0;
int ans = 0;//记录答案
int curFurDis = 0;//记录当前能走到的最远距离
int nextFurDis = 0;//记录下一步能走到的最远距离
for(int i = 0; i < nums.size(); i++)
{
//先计算i的位置能到达的最远位置是否可以更新下一步能走到的最远位置
nextFurDis = max(i + nums[i], nextFurDis);
if(i == curFurDis)//如果i遍历到了当前能走的最远位置，那么步数+1
{
ans++;
//更新当前i能走到的最远位置
curFurDis = nextFurDis;
//如果走了i这一步就能走到底了(确切的说不是在i下标走的这一步，可能是在i之前某一个下标但一定是在上一个i之后)
if(curFurDis >= nums.size() - 1) break;
}
}
return ans;
}
};
他这个思路是贪心，最多只用遍历一遍nums数组，需要两个变量进行判断。
注意nums只有1个数字时候的情况，需要特判。