当前位置:   article > 正文

leetcode-跳跃游戏&跳跃游戏Ⅱ_lecode 跳跃游戏

lecode 跳跃游戏

(代码题解来源于leetcode,非本人题解)

55. 跳跃游戏 - 力扣(LeetCode)

思路:

计算位置i可以跳的区间k,在跳的区间k中,找到可以跳到最大位置的区间Math.max(k, temp);,一直计算最远的可跳区间,如果nums.length - 1在最终的最远可跳区间内,那么return true;

public static boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }
        //前n-1个元素能够跳到的最远距离
        int k = 0;
        for (int i = 0; i <= k; i++) {
            //第i个元素能够跳到的最远距离
            int temp = i + nums[i];
            //更新最远距离
            k = Math.max(k, temp);
            //如果最远距离已经大于或等于最后一个元素的下标,则说明能跳过去,退出. 减少循环
            if (k >= nums.length - 1) {
                return true;
            }
        }
        //最远距离k不再改变,且没有到末尾元素
        return false;
    }

c++版本

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) return false;
            k = max(k, i + nums[i]);
        }
        return true;
    }
};

45. 跳跃游戏 II - 力扣(LeetCode)

谁说这题简单!!! (ㄒoㄒ),下周回来再看一遍吧

回来了。。

思路:

1.第一步是必须要跳的,第一步界定了可跳的范围,start=0,end=1;

2.从第一步开始,需要判定max(maxPos, i + nums[i]),知道下一步可以跳到最远的距离;同时,将start=end; end = maxPos + 1;

3. ans++; 跳跃次数

int jump(vector<int> &nums)
{
    int ans = 0;
    int start = 0;
    int end = 1;
    while (end < nums.size())
    {
        int maxPos = 0;
        for (int i = start; i < end; i++)
        {
            // 能跳到最远的距离
            maxPos = max(maxPos, i + nums[i]);
        }
        start = end;      // 下一次起跳点范围开始的格子
        end = maxPos + 1; // 下一次起跳点范围结束的格子
        ans++;            // 跳跃次数
    }
    return ans;
}

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/人工智能uu/article/detail/927881
推荐阅读
相关标签
  

闽ICP备14008679号