跳跃游戏 I - VII

55. 跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 0 就是坑，看能不能跳过去
        # if all(nums): return True
        n, right = len(nums), 0 # 最大覆盖范围
        for i, x in enumerate(nums):
            # 说明掉进坑了
            if i > right: return False 
            right = max(right, i + x)                 
            if right >= n - 1: return True
1
2
3
4
5
6
7
8
9
10

45. 跳跃游戏 II

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        # [2,3,1,1,4]
        # 起跳点从索引 0 开始，最远可跳到 2，更新 maxPos = 2, 此时 end = 2;
        # 起跳点可以是索引 1 or 2, 最远可跳到 4, 完成跳跃。
        maxPos, end, step = 0, 0, 0
        for i, x in enumerate(nums[:-1]):
            if i + x > maxPos:
                maxPos = i + x
            if i == end: # 完成一次跳跃
                end = maxPos
                step += 1
        return step
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1306. 跳跃游戏 III

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
    
        def f(i):
            x = arr[i]
            if not x: return True
            vis.add(i)
            for j in [i + x, i - x]:
                if 0 <= j < n and j not in vis:
                    if f(j): return True
            return False
            
        vis = set()
        n = len(arr)
       
        return f(start)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1345. 跳跃游戏 IV

数组可以抽象为一个无向图，数组元素为图的顶点，相邻或值相同的元素之间有一条无向边相连。每条边的权重都为 1，即此图为无权图。求从第一个元素到最后一个元素的最少操作数，即求从第一个元素到最后一个元素的最短路径长度。

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        d, q, vis, n = defaultdict(list), deque([[0, 0]]), set([0]), len(arr)
        for i, val in enumerate(arr): d[val].append(i)
        while q:
            idx, step = q.popleft()
            if idx == n - 1: return step
            v = arr[idx]
            step += 1
            if idx > 0 : d[v].append(idx - 1)
            if idx < n - 1: d[v].append(idx + 1)
            for i in d[v]: # 与 idx 相邻或相同元素之间一步可达。
                if i not in vis:
                    q.append([i, step])
                    vis.add(i)
            del d[v] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        d = defaultdict(set)
        for i, x in enumerate(arr):
            d[x].add(i)
        vis = set()
        step = 0
        q = {0, }
        while q: # 谁先到谁最短     
            if n-1 in q: return step
            tmp = set()
            for i in q:                       
                vis.add(i)
                if i: tmp.add(i-1)
                tmp.add(i+1)
                tmp.update(d[arr[i]])
                d.pop(arr[i])
            step += 1
            q = tmp - vis            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1340. 跳跃游戏 V

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:

        def dfs(i):
            if q[i] != -1: return
            q[i] = 1
            j = i - 1
            while j >= 0 and i - j <= d and arr[i] > arr[j]:
                dfs(j)
                q[i] = max(q[i], q[j] + 1)
                j -= 1
                
            j = i + 1
            while j < n and j - i <= d and arr[i] > arr[j]:
                dfs(j)
                q[i] = max(q[i], q[j] + 1)
                j += 1
                
        n = len(arr)
        q = [-1] * n
        for i in range(n):
            dfs(i)
       
        return max(q)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1696. 跳跃游戏 VI

1871. 跳跃游戏 VII

LCP 09. 最小跳跃次数

1654. 到家的最少跳跃次数

剑指 Offer 10- II. 青蛙跳台阶问题

975. 奇偶跳

403. 青蛙过河

1377. T 秒后青蛙的位置

935. 骑士拨号器

1728. 猫和老鼠 II