Leetcode 1871. Jump Game VII

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

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 = 0while 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 Truequeue.append(i)return False

Reference

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