-邵阳网络公司-邵阳网站建设|邵阳网站制作,推广网站建设语句,微信微网站是什么,软考中级科目难度排行【问题描述】[Leedcode][JAVA][第45题][跳跃游戏 II]
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置#xff0c;跳 1 步#xff0c;然后跳 3 步到达数组的最后一个位置。【解答思路】
1. 动态规划 超时
第 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; ilen ;i){temp[i] 0;}//初始化第一跳for(int i 1; (inums[0]) (ilen);i){temp[i];}//动态规划for(int i 1; ilen-1 ;i){//注意边界for(int ji1; (jnums[i]i) (jlen-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/
