給你一個非負整數陣列 nums ，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
假設你總是可以到達陣列的最后一個位置，
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2，
從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，
剛開始用的深搜，結果超時了emmm，而后轉用貪心，在每一次從起始位置到perEnd的程序中動態更新所能走到的最遠位置的下標，當每走到當前邊界時，更新邊界為最遠處下標并將步數+1.
由題設 “一定能到達目標”，設回圈次數為 nums.length-1 次以防止當 邊界值為nums.length-1 即恰好走到盡頭時步數仍+1的情況
public int jump(int[] nums) {
int step = 0;
int maxPosition = 0;
int perEnd = 0;
// 因無論如何都能訪問到最后一位，故跳過最后一位防止邊界==nums.length時導致step+1
for (int i = 0; i < nums.length-1; ++ i) {
maxPosition = Math.max(maxPosition, i+nums[i]);
if (i == perEnd) {
perEnd = maxPosition;
++ step;
}
}
return step;
} ??????? ??????? ???????
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301371.html
標籤：其他