LeetCode之Jump Game II
- 在LeetCode上刷的第三题，尝试了几种方法，最后还是选择贪心，复杂度为O(n)，个人感觉有不少的收获。
- 该题的题目是这样的，给定一个非负整数数组，每个元素代表着在当前位置最大能跳多少步，而我们的目标是从第一个位置开始，通过最少的步数到达最后一个位置。例如，给定数组是 A = [2,3,1,1,4]，则只需两步就能到达终点（第一个位置跳1步到达第二个位置，第二个位置上跳三步到达最后一个位置）。
- 首先，我想着用动态规划做的，设f(n)为从n位置出发到达终点所需的最少步数，那么f(n)的表达式为
- 然而，这个算法的复杂度可能是O(n2)O(n^2)，因为它重复算了一些没用的元素的步数，而且使用递归不断重复压栈出栈性能也会有影响。
- 然后，我接着想出另一种反向动态规划，首先遍历一次A，找出那些能一步到达终点的位置，在这些位置中选出最小的一个，以它作为新的终点继续上一步操作，直至最小的位置为0，算法结束。可惜，这种算法对于全是1的数组复杂度为O(n2)O(n^2)，因为每次迭代我们都需要遍历一次数组。
- 最后，还是利用贪心的思想，感觉自己一开始走了弯路，贪心照理说是第一个需要考虑的~，主要思想是，初始化scope为A[0]，遍历的初始位置fromIndex为1，然后通过判断在fromIndex到scope范围内，找出新的最大的scope，如果新的scope大于终点的index，那么算法结束，否则fromIndex=原来scope+1，scope=新的scope，重新计算上一步。这样算法的复杂度就只是O(n)O(n)，因为最坏的情况也是只需遍历一次数组就搞定了。
- 因为才刚开始刷OJ，笔者目前仍然是算法的小白，不过通过这一题确实让我收获不少，知道了算法设计的考虑顺序和一些基本逻辑。希望对大家也会有所帮助。
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() <= 1){
return 0;
}
int firstNum = nums[0];
if (firstNum == 0){
return 0;
}
int scope = firstNum;
int step = 0;
int from = 1;
while (scope < nums.size() - 1){
int currentScope = scope;
for (int i = from; i <= scope; i++){
if (currentScope < i + nums[i])
currentScope = i + nums[i];
}
step++;
from = scope + 1;
scope = currentScope;
}
return step + 1;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年08月27日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读