45. Jump Game II
给定一个非负整数的数字, 你开始在数组的第一个索引处
每一个在数组中的元素代表你能够跳跃的最大距离
你的目标是找到到达最后一个索引的最小跳跃数
my code
要达到最小跳跃数的话, 那么只要保证每次跳跃的距离是最大的就可以了
每个节点的跳跃距离是 节点距离起始节点的距离 + 节点自身值
感觉比上一个 jump 简单
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
| class Solution {
public:
int jump(vector<int>& nums) {
size_t size = nums.size();
if (size <= 1) return 0;
int route = 0;
for (int i = 0; i < size; ) {
if (i + nums[i] >= size - 1)
return ++route;
int maxn = nums[i] + nums[i + nums[i]];
int step = nums[i];
for (int i2 = i + 1; i2 <= (i + nums[i]); ++i2) {
if (i2 - i + nums[i2] > maxn) {
maxn = i2 - i + nums[i2];
step = i2 - i;
}
}
i += step;
++route;
}
return -1;
}
};
|
结果还行, 看一下最好的算法
the best solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| auto fast_io = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, n);
ans[0] = 0;
for (int i = 0; i < n; ++i) {
if (nums[i]+i >= n-1) ans[n-1] = min(ans[n-1], ans[i]+1);
else {
int temp = nums[i];
while (temp > 0 && ans[i+temp] > ans[i]+1) ans[i+(temp--)] = ans[i]+1;
}
}
return ans[n-1];
}
};
|
大致想法上好像差不多
看不太懂, 但是我感觉好像差不多
它多了一个长度为 n 的数组, 并且循环是线性 n
(我没有使用数组, 并且循环是以 step 为距离, 唯一会在速度上决胜负的应该是我for 中的 for 和他for中的while对比, 他的while可以提前退出的, 综合来说, 我觉得这次我的算法不输他! (有点膨胀 :) … ) )
我将前面的 fast_io 添加进我的代码后, 也达到了最好的速度
emmm, 那就不花时间研究他的算法了~