跳跃游戏修正
跳跃游戏修正
提问于 2017-11-07 01:32:39
我不知道如何改进跳转游戏问题(https://leetcode.com/problems/jump-game/description/) .It的解决方案，这在逻辑上似乎是正确的，但对于[nums=1,1,1,1,1,1,1，.]这样的大输入，我遇到了java.lang.Stackoverflow错误。
我知道我由于太多的递归调用而溢出，我如何优化它？
class Solution {
public boolean canJump(int[] nums) {
int []f = new int[1];
f[0] = 0;
return help(nums,0,f);
}
public static boolean help(int[]nums, int c, int[] f) {
if(c==nums.length-1) {
f[0] =1;
return true;
}
if(f[0]==1) return true;
int val = nums[c];
for(int i = 1; i <= val; i++) {
if(f[0]==1) return true;
return help(nums,(c + i), f);
}
return false;
}
}回答 1
Stack Overflow用户
发布于 2022-03-02 14:44:50
这可以用贪婪算法在T:O(N)中解决：
class Solution {
public int jump(int[] nums) {
int res=0, l=0, r=0;
while(r<(nums.length-1)){
int farthest=0;
for (int i=l;i<r+1;i++){
farthest=Integer.max(farthest,i+nums[i]);
}
l=r+1;
r=farthest;
res++;
}
return res;
}
}解释
nums = [2,3,1,1,4]你跳两步。你得到了索引2，所以你跳过元素3,1。11月，你循环3,1并检查哪一个会带你到更远的地方。在本例中为3，然后更新变量。增加res=1
来自元素3，即索引-1。你跳3步，跳1,1,4步。现在通过1,1,4圈找到最远的。4.增加res=2。从out of循环开始，返回res=2。
- 它似乎有两个嵌套循环，但如果仔细看，总迭代是N。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/47148594
复制相关文章
相似问题
腾讯云开发者
