刷题记录——跳跃游戏

第一道题地址：
leetcode-jump-1
第二道题地址：
leetcode-jump-2

题目一

题解

def canJump(self, nums: List[int]) -> bool:
    long = len(nums)
    if long == 1: # 数组中只有一个数的时候，默认True
        return True

    max_jump = 0  # 跳跃最远的距离
    for i in range(long):
        temp = i + nums[i]  
        if temp > max_jump:  # 该点跳跃距离，更新最远距离
            max_jump = temp
        if (nums[i] == 0) & (i == max_jump) & (i < long - 1):  # 中途停止更新下一条的条件
            return False
    
    return True # 其他情况都可以为真

结果：内存beat 8.31%

题目二

题解

class Solution:
    def jump(self, nums: List[int]) -> int:

        long = len(nums)
        jump, max_jump, end = 0, 0, 0
        for i in range(long - 1):
            if max_jump >= i:
                # 更新值
                max_jump = max(max_jump, i + nums[i])
                # 跳
                if i == end:
                    jump += 1
                    end = max_jump
        return jump

这道题最开始想得太复杂，想每一步怎么跳，跳到哪里，更新那些值。看了题解之后，才知道其实不用这么麻烦，只用判断i的落点，如果和上一次跳完更新的end值相等，可以再一次跳。