題目描述（傳送門）
給定一個非負整數陣列，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2，
從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，
解題思路&代碼實作
思考
從第0位置，最少需要跳幾次達到最后一個位置？
如果希望最少跳躍達到終點，則需要明確何時進行跳躍是最合適的，
例如：在到達i位置前：
貪心規律
在到達某點之前若一直不跳，發現從該點不能跳到更遠的地方了，在這之前肯定需要一次跳躍！并且需要選擇可以跳到更遠的位置的位置，
代碼
public int jump(int[] nums) {
if (nums.length < 2) {
return 0;
}
int current_max_index = nums[0];// 當前可到達的最遠位置
int pre_max_max_index = nums[0];// 遍歷各個位置程序中，可到達最遠位置
int jump_min = 1;
for (int i = 1; i < nums.length; i++) {
if (i > current_max_index) {// 若無法再向前移動了，才進行跳躍
jump_min++;
current_max_index = pre_max_max_index;//更新當前可達到的最遠位置
}
if (pre_max_max_index < nums[i] + i) {
pre_max_max_index = nums[i] + i;
}
}
return jump_min;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257184.html
標籤：其他
上一篇：多檔案實作掃雷