45. Jump Game II

Title

This problem is a continuation of the previous problem, Jump Game 44, where the previous problem was to find out if it is possible to reach the end, while the current problem is to calculate the minimum number of steps needed (under the premise that he must reach the last index).

Algorithm

This is a simple question at first, thinking that each step is maximized and the number of steps taken at the end is the answer, which is obviously undesirable, because you may skip a node with a long step at a certain step. For example nums = [2,3,1,1,4], if you follow my algorithm, 2-1-1-4 takes three steps, but if you go to the node 3, 2-3-4 only takes 2 steps, so obviously there is something wrong with my previous algorithm.

Then I wondered if I should go through the nodes one by one, but I didn't find a good way to keep track of the minimum number of steps in this place. So my previous problem was actually how to traverse the elements while still making sure that I could record the maximum number of steps per hop correctly and clearly.

Define a far or maxReach that records the farthest distance that can be traveled with each jump, then our traversal endpoint is here; after reaching this endpoint, the number of steps is added by one. This represents the farthest distance that can be reached in one jump. Then we continue the traversal, re-record the farthest distance of the next far, and find the end of the next jump. Just follow this logic to the end.

Just return the result in the end.

Code

class Solution {
    public int jump(int[] nums) {
        int res = 0.
        int end = 0.
        int far = 0.
        for (int i = 0; i < nums.length - 1; i++) {
            far = Math.max(far, nums[i] + i).
            if (i == end) {
                res++.
                end = far.
            }
        }
        return res.
    }
}

题目

这个题目是上一个题目44题Jump Game的延续，之前的题目只是让求是否可以到达最后即可，而当前题目让计算最少需要几步（在保证他一定可以到达最后一个index的前提下）。

算法

这个题目一开始想简单了，就是想着每一步最大化，到终点时走的步数就是就是答案，这明显是不可取的，因为你可能在某一步的时候跳过一个步长很长的节点。例如nums = [2,3,1,1,4]，如果按照我这个算法，2-1-1-4需要三步，其实如果走到3这个节点的话，2-3-4只需要2步，那明显我的之前的算法就有一些问题。

然后我又想 那是不是要一个个去走那些节点，但是这个地方我并没有找到一个好的方式去记录最少步数。所以我之前的问题其实是如何在遍历元素的同时，还能确保能够正确清晰的记录每次跳的最大步数。

定义一个far或者叫maxReach，记录更新每次跳能够走到的最远距离，那么我们这次的遍历终点end就在这里；到达这个终点后，步数加一。这里代表的是一次跳跃到了最远距离。然后我们继续遍历，重新记录下一次的far最远距离，找到下一跳的终点。按照这个逻辑走到最后即可。

最终返回结果即可。

代码

class Solution {
    public int jump(int[] nums) {
        int res = 0;
        int end = 0;
        int far = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            far = Math.max(far, nums[i] + i);
            if (i == end) {
                res++;
                end = far;
            }
        }
        return res;
    }
}