文章目錄

• • 1：題目描述
  • 2：解決方法

1：題目描述

• 給一個元素非負的數組，你開始是在第一個元素上
• 每一個元素都代表你在當前位置最大可跳的長度
• 你的目標是到達最后一個位置，用最小的跳數
• 你總是可以到達最后一個元素

2：解決方法

• 貪心
  • 每次找到nums[i]+i 最大的下表元素
  • 當i+j>= nums.length-1 的時候，就可以退出了

class Solution {public int jump(int[] nums) {if(nums.length<2) return 0;int i=0,j=nums[0],result=0;for(;i<nums.length && i+j<nums.length-1;){ // 此時K 是跑的最遠的地方result++;i=getMaxIndex(nums,i,i+j);j=nums[i];/*當他自己能成為觸摸到最后一個的時候，就沒有必要選擇最大的了*/}if(i!=nums.length-1) result++;return result;}public int getMaxIndex(int[] nums,int i,int j){int result=i,value=nums[result]+result;for(i=i+1;i<= j;i++){ // System.out.println(i);if(nums[i]+i> value){result=i;value=nums[result]+result;}}return result;} }

index :0

3 1

inedx :1 4

nums[0] nums[1]

此時的結果就是2

找什么最大

• nums[i]+i 的最大值
• nums[i]+i 的數值據代表 你在index 為i 的時候，最大可以跳到的weizhi j

在 [i+1,i+nums[i]] 找到 nums[j]+j 最大的數字

3 1 1

2 3 1

總結

以上是生活随笔為你收集整理的45 jump game II（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。