Leetcode面试经典150题-45.跳跃游戏II
解法都在代码里，不懂就留言或者私信，这个题绝对比动态规划的解法强
class Solution {/**本题我们先不用动态规划了，因为从任何一个位置都可能跳到最后一个位置，用动态规划的成本太高了本题的解题思路：看看某个步数内最多能跳到多远，如果某步内能涵盖最后一个位置，那这个就是最小的步数 */public int jump(int[] nums) {/**你就在终点，跳啥啊 */if(nums.length == 1) {return 0;}/**否则是需要跳的，至少一步，我们定义两个变量curStep代表当前跳的步数curMax代表当前步数最多可以跳多远,比如0位置的值是3，那就是curStep是1，curMax是3代表一步之内最多能跳到3*/int curStep = 1;int curMax = nums[0];/**假设再多跳一步能跳到多远 */int nextStepMax = 0;for(int i = 1; i < nums.length; i++) {/**如果curStep覆盖不了，那就得多跳一步，curStep++同时看看 */if(i > curMax) {curStep ++;/**之前已经计算过多跳一步最远可以跳到哪里了，放在了nextStepMax*/curMax = nextStepMax;/**这里注意nextStepMax也要更新 */nextStepMax = Math.max(nextStepMax,i + nums[i]);} else {/**当前在curStep的覆盖范围内，如果让我多跳一步，我最多可以跳多远，在当前覆盖范围内看看i+nums[i]会不会比原来的nextStepMax大，谁大取谁*/nextStepMax = Math.max(nextStepMax,i + nums[i]);}/**如果当前步数可以到达最后了，直接返回 */if(curMax >= nums.length - 1) {break;}}return curStep;}
}运行结果
