Leetcode——45. Jump Game II

題目原址

https://leetcode.com/problems/jump-game-ii/description/

題目描述

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.

Example:

Input: [2,3,1,1,4]

Output: 2

Explanation: 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.

解題思路

該題比Leetcode——55. Jump Game題稍微難一些，這個題需要使得到達終點的跳躍步數最少，并且題目說假設可以到達終點。是以這裡面要有3個變量。一個是用來存儲跳躍的步數

ret

；一個是用來存儲目前最遠能夠到達的位置

CurMaxReach

；一個是用來存儲上一步能夠最遠到達的位置

LastMaxReach

。在每次循環中都要判斷目前位置是否大于上一步能最遠到達的位置，如果能，則更改

LastMaxReach

的值為

CurMaxReach

并将步數增加1，然後要更改

CurMaxReach

的值。

AC代碼

class Solution {
    public int jump(int[] nums) {
        int ret = ; //傳回的步數
        int CurMaxReach = ; //最遠能到達的位置
        int LastMaxReach = ; //上一步最遠能到達的位置

        for(int i = ; i < nums.length; i++) {
            //永遠也達不到終點 {3，2，1，0，4}
            if(i > CurMaxReach)
                return -;
            //目前能到的位置大于上一步最遠能達到的位置，是以要更新上一步能到達的位置，并将步數+1
            if(i > LastMaxReach) {
                LastMaxReach = CurMaxReach;
                ret++;
            }
            //更新最遠能到達的位置
            CurMaxReach = Math.max(CurMaxReach, i + nums[i]);
        }
        return ret;        
    }
}