題目來源
45. 跳躍游戲 II
題目詳情
給定一個長度為 n 的 0 索引整數陣列 nums，初始位置為 nums[0]，
每個元素 nums[i] 表示從索引 i 向前跳轉的最大長度，換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:
0 <= j <= nums[i]i + j < n
回傳到達 nums[n - 1] 的最小跳躍次數，生成的測驗用例可以到達 nums[n - 1]，
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2，
從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 題目保證可以到達
nums[n-1]
相似題目
55. 跳躍游戲
題解分析
本題與[55. 跳躍游戲]這題不同，不能使用相同的貪心思路來解決，這里需要求解的問題是最小的跳躍次數，而要求解最小的跳躍次數需要每次在跳躍時選擇盡可能跨度大的格子，
換句話說，只需要判斷哪一個選擇最具有「潛力」即可：
比如上圖這種情況，我們站在索引 0 的位置，可以向前跳 1，2 或 3 步，你說應該選擇跳多少呢？
顯然應該跳 2 步調到索引 2，因為 nums[2] 的可跳躍區域涵蓋了索引區間 [3..6]，比其他的都大，如果想求最少的跳躍次數，那么往索引 2 跳必然是最優的選擇，
你看，這就是貪心選擇性質，我們不需要「遞回地」計算出所有選擇的具體結果然后比較求最值，而只需要做出那個最有「潛力」，看起來最優的選擇即可，
i 和 end 標記了可以選擇的跳躍步數，farthest 標記了所有選擇 [i..end] 中能夠跳到的最遠距離，jumps 記錄了跳躍次數，
本演算法的時間復雜度 O(N)，空間復雜度 O(1)，
java實作
class Solution {
public int jump(int[] nums) {
int right = 0, maxStep = 0, len = nums.length;
int steps = 0;
for (int i=0; i<len-1; i++) {
maxStep = Math.max(maxStep, nums[i] + i);
if (i == right) {
right = maxStep;
steps++;
}
}
return steps;
}
}
參考
如何運用貪心思想玩跳躍游戲
Either Excellent or Rusty轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544320.html
標籤：Java
上一篇：day14-例外處理
下一篇：05-python運算子