Leetcode 1871. Jump Game VII

Tyan

发布于 2021-08-13 11:41:52

3310

发布于 2021-08-13 11:41:52

文章被收录于专栏：SnailTyan

1. Description

2. Solution

**解析：**Version 1，使用队列来保存可进行下一次检索的候选索引，从第0的位置开始检索，根据minJump和maxJump确定检索范围，如果当前字符为0，则将索引添加到队列中，如果恰好是最后一个位置，返回True。下一次的检索范围不能直接从index+minJump开始，因为有可能会造成重复检索，因此取max(index+minJump, end)，end为上一次检索的最后位置，这样检索的时间复杂度为O(n)。

Version 1

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        queue = collections.deque()
        queue.append(0)
        end = 0
        while queue:
            index = queue.popleft()
            start = max(index+minJump, end)
            end = min(index+maxJump+1, len(s))
            for i in range(start, end):
                if s[i] == '0':
                    if i == len(s) - 1:
                        return True
                    queue.append(i)
        return False