Jump Game II

发表于   |   分类于 ， ，

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

描述

一个非负整型数组，每个值代表能行走的步数，停留在哪个值上，便代表下一次能行走几步，假设一定能从第一个点到达最后一个点，求最少的停留次数

分析

前提：一定能从第一个点达到最后一个点
保证：每一步都走得最远
假设第一步能到达的最远距离为 r，只需要在 0 ~ r 之间找到能走的最远的作为下一步，更新 r，并且次数 + 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int jump(int[] nums) {

        int r = 0;
        int max = 0;
        int count = 0;

        for (int i = 0; i < nums.length; i++) {

            max = Math.max(max, nums[i] + i);

            if (i >= r && i != nums.length - 1) {
                count++;
                r = max;
            }
        }

        return count;
    }
}