跳跃游戏(一)

C++ 解法, 执行用时: 33ms, 内存消耗: 6508KB, 提交时间: 2021-12-04

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool canJump(vector<int>& nums) {
        // write code here
        int len=nums.size();
        if(len==1)
            return true;
        int tmp=nums[0];
        for(int i=0;i<=tmp;i++){
            tmp=max(tmp,i+nums[i]);
            if(tmp>=len-1)
                return true;
        }
        return false;
    }
};

C++ 解法, 执行用时: 33ms, 内存消耗: 6520KB, 提交时间: 2022-01-29

class Solution {
public:
    /*
    方法一：贪心
    
    解题思路：
    1. 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
    2. 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
    3. 如果可以一直跳到最后，就成功了

    复杂度分析
    时间复杂度：O(n)
    空间复杂度：O(1)

    参考：
    https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/
    */
    bool canJump1(vector<int>& nums) {
        if (nums.size() == 0) {
            return false;
        }
        //前n-1个元素能够跳到的最远距离
        int k = 0;
        for (int i = 0; i <= k; i++) {
            //第i个元素能够跳到的最远距离
            int temp = i + nums[i];
            //更新最远距离
            k = max(k, temp);
            //如果最远距离已经大于或等于最后一个元素的下标,则说明能跳过去,退出. 减少循环
            if (k >= nums.size() - 1) {
                return true;
            }
        }
        //最远距离k不再改变,且没有到末尾元素
        return false;
    }

    //方法一代码精简版本
    bool canJump1_2(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;
    }

    /*
    方法一，另一种写法

    【性质】如果能够到达当前位置，那么也就一定能够到达当前位置的左边所有位置
    */
    bool canJump1_3(vector<int>& nums) {
        int k = 0; //k为当前能够到达的最大位置
        for(int i = 0; i < nums.size(); i++){
            if(i > k) return false;//【关键】遍历元素位置下标大于当前能够到达的最大位置下标，不能到达
            //能够到达当前位置，看是否更新能够到达的最大位置k
            k = max(k, i + nums[i]);
        }
        //跳出则表明能够到达最大位置
        return true;
    }

    /*
    方法一，另一种实现
    每一步都计算一下从当前位置最远能够跳到哪里，然后和一个全局最优的最远位置 farthest 做对比，
    通过每一步的最优解，更新全局最优解，这就是贪心。

    参考：
    https://labuladong.gitee.io/algo/3/27/107/
    */
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int farthest = 0;
        for (int i = 0; i < n - 1; i++) {
            // 不断计算能跳到的最远距离
            farthest = max(farthest, i + nums[i]);
            // 可能碰到了 0，卡住跳不动了
            if (farthest <= i) {
                return false;
            }
        }
        return farthest >= n - 1;
    }

    /*
    方法二：动态规划（超时）
    */
    bool canJump2(vector<int>& nums) {
        int n = nums.size();
        vector<bool> F(n, 0);
        //初值条件
        F[0] = true;
        //递推方程
        for(int k = 1; k < n; k++) {
            for(int j = 0; j < k; j++) {
                if(F[j] == true && k - j <= nums[j]) {//【易错】nums[j]为可以跳跃的最大长度
                    F[k] = true;
                    break;
                }
            }
        }
        return F[n - 1];
    }
};

C++ 解法, 执行用时: 34ms, 内存消耗: 6412KB, 提交时间: 2022-02-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool canJump(vector<int>& nums)
    {
        int len = nums.size();
        int temp = 0;
        
        for(int i=0; i<len; ++i)
        {
            if(i > temp) return false;
            temp = max(temp, i + nums[i]);
            if(temp >=len-1)
                return true;
        }

        return false;
    }
};

C++ 解法, 执行用时: 34ms, 内存消耗: 6508KB, 提交时间: 2021-11-29

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool canJump(vector<int>& nums) {
        // write code here
        
        if(nums.size()==1)return true;
         
        int tmp=nums[0];
        for(int i=1;i<=tmp;i++){
             
            tmp=max(tmp,i+nums[i]);
             
            if(tmp>=nums.size()-1)return true;
        }
         
        return false;
        
        
    }
};

C++ 解法, 执行用时: 34ms, 内存消耗: 6508KB, 提交时间: 2021-11-18

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool canJump(vector<int>& nums) {
        // write code here
        if(nums.size() < 2) return true;
        int jump = 0;
        for(int i = 0; i <= jump; i++)
        {
            jump = max(jump, i + nums[i]);
            if(jump >= nums.size() - 1) return true;
        }
        return false;
    }
};

详情