#|【Leetcode贪心区间问题二】45. 跳跃游戏 II
文章目录
- Leetcode45
-
- 1.问题描述
- 2.解决方案
Leetcode45 1.问题描述
文章图片
2.解决方案
思路关键在于：在当前步覆盖范围内找一个下一步能走最远的，作为下一步的选择！
官方说法：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖到了终点！
文章图片
代码实现也思路清晰
1.在i<=curDistance范围内找到最大的nextDistance
2.在i==curDistance进行判断要不要再走一步
2.1 不用走了
2.2 再走一步
2.3 剪枝，如果这到终点了直接返回(这一步不一定会提升效率说实话)
代码实现有个注意的点，官方的curDistance初始化是为零，我初始化为了nums[0]，其实都可以，初始化为零不过就是第一次循环后把nums[0]赋给了curDistance，效果一样的
class Solution {public:
int jump(vector& nums) {if(nums.size()==1) return 0;
int ans=1;
int curDistance=nums[0];
int nextDistance=0;
for(int i=1;
i=nums.size()-1) return ans;
}
}return ans;
}
};
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长