leetcode55、45.跳跃游戏 I&II

我不是女神ヾ 2023-01-23 13:48 188阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]

*  如果某一个作为起跳点的格子可以跳跃的距离是3，那么表示后面的3个格子都可以作为。
 *  可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
 *  如果可以一直跳到最后，就成功了。否则在过程中返回false退出

/** * @param {number[]} nums * @return {boolean} */
    var canJump = function(nums) { 
        let range = 0;
        for(let i=0;i<nums.length;i++){ 
            if(i>range){ 
                return false;
            }
            range = Math.max(range,nums[i]+i);
            
        }
        return true;
    };

时间复杂度On  
空间复杂度O1

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]

遍历一个可抵达的区间，从中选出能跳最远的点，就有了新的可抵达的区间，然后跳跃一次，进入新的区间继续遍历寻求最优解

时间复杂度On  
空间复杂度O1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221004/cf5078ec37974e7082ee31783e01ef8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221004/e7eaaf9a3be34ef5b26c9a03207be7ca.png