55. Jump Game

https://leetcode.com/problems/jump-game/

solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if not nums:
            return False
        if len(nums) == 1:
            return True

        i = 0
        res = 0  # 目前能覆盖的最大范围

        while i <= res:  # 注意是 <=
            res = max(res, i + nums[i])
            if res >= len(nums) - 1:
                return True
            i += 1

        return False

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

follow up-jump game系列

45 Jump Game II

• 记录当前覆盖最远距离和下一次覆盖最远距离，当前距离最远时，增加一步到下一次最远距离

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0

        cur_pos = 0
        next_pos = 0
        res = 0
        for i in range(len(nums)):
            next_pos = max(i+nums[i], next_pos)
            if i == cur_pos:
                cur_pos = next_pos
                res += 1
                if next_pos >= len(nums) - 1:
                    break
        return res

时间复杂度：O() 空间复杂度：O()

• 动态规划

class Solution:
    def jump(self, nums: List[int]) -> int:
        res = [float('inf')] * len(nums)
        res[0] = 0

        for i in range(len(nums)):
            for j in range(i, i+nums[i]+1):
                if j < len(nums):  # 注意边界
                    res[j] = min(res[j], res[i]+1)  # 递推是根据业务含义来的
        return res[-1]

时间复杂度：O() 空间复杂度：O()

1306. Jump Game III

• bfs

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        status = [False] * len(arr)
        status[start] = True

        queue = collections.deque()
        queue.append(start)

        while queue:
            index = queue.popleft()
            status[index] = True
            if arr[index] == 0:
                return True

            if 0 <= index + arr[index] < len(arr):
                if not status[index + arr[index]]:
                    queue.append(index + arr[index])

            if 0 <= index - arr[index] < len(arr):
                if not status[index - arr[index]]:
                    queue.append(index - arr[index])
        return False

• dfs

1345. Jump Game IV

1340. Jump Game V

# https://www.1point3acres.com/bbs/thread-746704-1-1.html

1696. Jump Game VI

1871. Jump Game VII

# 滑动窗口+DP: https://zhuanlan.zhihu.com/p/474961276

• 超时

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        if s[-1] != '0':
            return False

        nums = [0]
        for i, char in enumerate(s[1:]):
            if char == '0':
                nums.append(i+1)

        dp = [False] * len(nums)
        dp[0] = True

        for i in range(1, len(nums)):
            for j in range(i):
                if dp[j] and minJump <= nums[i] - nums[j] <= maxJump:
                    dp[i] = True
                    break
        return dp[-1]

*2297. Jump Game VIII