LeetCode日常-困难-403. 青蛙过河

本文最后更新于：2021年5月4日 中午

题目

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）

开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

示例 1:

1
2
3
4
5
6
7
8
9
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：
跳 1 个单位到第 2 块石子  
跳 2 个单位到第 3 块石子  
跳 2 个单位到第 4 块石子  
跳 3 个单位到第 6 块石子  
跳 4 个单位到第 7 块石子  
跳 5 个单位到第 8 个石子

示例 2：

1
2
3
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去

个人解法

记忆化搜索 + 二分查找
遍历每一块石头，二分法寻找能到达的下一块石头，保存到达下一块石头后的速度
判断最后一块石头有没有记录速度即可知道能不能通过 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        stones_speeds = [{0}]
        river_len = len(stones)
        for i in range(1, len(stones)):
            if stones[i] > i + stones[i-1]:
                return False
            else:
                stones_speeds.append(set())

        for stone_index, stone in enumerate(stones):
            # 遍历当前位置可能的速度
            for stone_speed in stones_speeds[stone_index]:
                # 二分法查找目标石头是否存在
                for next_speed in (stone_speed - 1, stone_speed, stone_speed + 1):
                    next_stone = stone + next_speed
                    if next_stone <= stone or next_stone > stones[river_len - 1]:
                        continue
                    left, right = stone_index + 1, river_len - 1
                    while left <= right:
                        avg_index = (left + right) // 2
                        if stones[avg_index] == next_stone:
                            # 为下一块石头设置信息
                            stones_speeds[avg_index].add(next_speed)
                            break
                        elif stones[avg_index] > next_stone:
                            right = avg_index - 1
                        else:
                            left = avg_index + 1
        return bool(stones_speeds[-1])

大佬解法-动态规划

关键 定义dp为字典，其中key=stone, value={可以到达stone的跳跃步长组成的集合}
那么能够到达stone等价于dp[stone]非空。

1
2
3
4
5
6
7
8
9
10
def canCross(stones: List[int]) -> bool:
    set_stones=set(stones)
    dp = defaultdict(set)
    dp[0]={0}
    for s in stones:
        for step in dp[s]:
            for d in [-1,0,1]:
                if step+d>0 and s+step+d in set_stones:
                    dp[s+step+d].add(step+d)
    return len(dp[stones[-1]])>0