【問題描述】[Leedcode][JAVA][第45題][跳躍游戲 II]

輸入: [2,3,1,1,4] 輸出: 2 解釋: 跳到最后一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數組的最后一個位置。

【解答思路】

1. 動態規劃 超時

第 1 步：設計狀態 int[] temp = new int[len];
第 2 步：狀態轉移方程

• 沒跳過 temp[j]=temp[i]+1
• 跳過 temp[j] = Math.min( temp[j],temp[i]+1 );
  第 3 步：考慮初始化
  temp數組置0 第一跳
  第 4 步：考慮輸出
  temp[len-1]
  時間復雜度：O(N^2) 空間復雜度：O(N)

public int jump(int[] nums) {int len = nums.length;if(len == 0 ||len ==1){return 0;}int[] temp = new int[len];//輔助數組置0for(int i =0; i<len ;i++){temp[i] = 0;}//初始化第一跳for(int i =1; (i<=nums[0]) && (i<len);i++){temp[i]++;}//動態規劃for(int i =1; i<len-1 ;i++){//注意邊界for(int j=i+1; (j<=nums[i]+i)&& (j<=len-1);j++){//跳過 比較當前到達j位所在步數 與 起跳格i所在步數+1 之間的大小if(temp[i]+1 < temp[j]){temp[j]=temp[i]+1 ;}//沒跳過 則是起跳格i所在步數+1if(temp[j]==0){temp[j]=temp[i]+1;}}}return temp[len-1];}

2. 反向查找位置 貪心

• 「貪心」地選擇距離最后一個位置最遠的那個位置，也就是對應下標最小的那個位置。
• 從左到右遍歷數組，選擇第一個滿足要求的位置。
  時間復雜度：O(N^2) 空間復雜度：O(1)

public int jump(int[] nums) {int position = nums.length - 1;int steps = 0;while (position > 0) {for (int i = 0; i < position; i++) {if (i + nums[i] >= position) {position = i;steps++;break;}}}return steps;}

3. 正向查找可到達的最大位置 降低時間復雜度

時間復雜度：O(N) 空間復雜度：O(1)

public int jump(int[] nums) {int end = 0;int maxPosition = 0; int steps = 0;for(int i = 0; i < nums.length - 1; i++){//找能跳的最遠的maxPosition = Math.max(maxPosition, nums[i] + i); if( i == end){ //遇到邊界，就更新邊界，并且步數加一end = maxPosition;steps++;}}return steps; }

【總結】

1.貪心算法，每次找局部最優，最后達到全局最優

2. 不要死板 想好方法 總有辦法實現 巧妙更新邊界

3. 畫圖思考 想清楚再動手

參考鏈接：https://leetcode-cn.com/problems/jump-game-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-10/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第45题][跳跃游戏 II][贪心算法]的全部內容，希望文章能夠幫你解決所遇到的問題。

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