Leetcode: Jump Game II
LeetCode II Game Jump
2023-09-11 14:14:08 时间
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
难度:89,这道题参考了网上的解法:和Jump Game很像,只是原来的全局最优现在要分成step步最优和step-1步最优(假设当前步数是step)。当走到超过step-1步最远的位置时,说明step-1不能到达当前一步,我们就可以更新步数,将step+1。时间复杂度仍然是O(n),空间复杂度也是O(1)。代码如下:
1 public class Solution { 2 public int jump(int[] A) { 3 if (A == null || A.length == 1) return 0; 4 int global = 0; 5 int steps = 0; 6 int lastreach = 0; 7 for (int i=0; i<=global && i<A.length; i++) { 8 if (i > lastreach) { 9 steps++; 10 lastreach = global; 11 } 12 global = Math.max(A[i]+i, global); 13 } 14 if (global < A.length-1) return 0; 15 else return steps; 16 } 17 }
相关文章
- Java实现LeetCode 5450. 满足条件的子序列数目(双指针)
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- Java实现 LeetCode 649 Dota2 参议院(暴力大法)
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- Java实现 LeetCode 446 等差数列划分 II - 子序列
- Java实现 LeetCode 240 搜索二维矩阵 II(二)
- Java实现 LeetCode 236 二叉树的最近公共祖先
- Java实现 LeetCode 212 单词搜索 II(二)
- Java实现 LeetCode 213 打家劫舍 II(二)
- Java实现 LeetCode 140 单词拆分 II(二)
- Java实现 LeetCode 82 删除排序链表中的重复元素 II(二)
- 【贪心】LeetCode 11. 盛最多水的容器【中等】
- LeetCode(95): 不同的二叉搜索树 II
- [LeetCode] Reverse Linked List(递归与非递归反转链表)
- [LeetCode] Find Minimum in Rotated Sorted Array II
- Leetcode.剑指 Offer II 022 链表中环的入口节点
- LeetCode-940. 不同的子序列 II【字符串,动态规划】
- 【LeetCode 中等 矩阵】498 对角线遍历
- Leetcode 2164. 对奇偶下标分别排序(可以,一次过)
- Leetcode 2206. 将数组划分成相等数对(可以,一次过)
- [LeetCode] 45. Jump game II ☆☆☆☆☆(跳跃游戏 2)
- LeetCode Triangle
- Best Time to Buy and Sell Stock I,II,III [leetcode]
- 【Leetcode刷题Python】122.买卖股票的最佳时机 II