[Leedcode][JAVA][第45题][跳跃游戏 II][贪心算法]

【问题描述】[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-/problems/jump-game-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-10/