【LeetCode】 45. 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:

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.

Solution

• 使用貪婪法，只在乎當下最遠可以到哪裡。
• 去紀錄、計算當下最遠可以到哪裡，如果你可以到第i格，代表你有能力可以到0~i的任何一格。
• 如果你已經在第i格，你下次就可以到i+nums[i]格。利用這點去不停更新最遠距離。
• 記住，不要去重複的格子試圖更新最遠距離，因為每一格提供給你的距離是固定的，因此計算過的格子就應該跳過。
  • 我下面的code利用last去紀錄上一次更新到哪裡。

Code

class Solution {
public:
    int jump(vector<int>& nums) {
        int step=0;
        int count=0;
        int next=0;
        int last=0;
        for(;step<nums.size()-1;count++)
        {
            for(int i=last;i<=step;i++)
            {
                if(i+nums[i]>next)
                {
                    next=i+nums[i];
                }
            }
            last=step;
            step=next;
        }
        return count;
    }
};

tags: LeetCode C++