leetcode 403 青蛙过河

77 阅读 0 评论 51 点赞

我是靠谱客的博主怕孤单柚子，这篇文章主要介绍leetcode 403 青蛙过河，现在分享给大家，希望可以做个参考。

每天坚持刷题！！！

leetcode 403 青蛙过河

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

给定石子的位置列表（用单元格序号升序表示），请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。开始时，青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。

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

石子的数量 ≥ 2 且 < 1100；
每一个石子的位置序号都是一个非负整数，且其 < 231；
第一个石子的位置永远是0。

题目分析：

这道题咋一看起来似乎无从下手，因为每一个石头到达的方法可能有多种，每一种方法下一步可以到达的石头又不一样，但是我们可以通过对每一个石头记录其从上一部到达时的跳过的步数，然后看最后终点的石头是否有到达的可能。
总结起来，就是搞一个hash表，每一个石头位置为key，value为一个set，记录可以到达这个位置的石头要跳过的上一步的步数，然后通过遍历每一个石头的set来得到可能到达的下一个石头的位置。
举例而言，假设石头为【0，1，2，3】，那么得到的这个hash表为：{0：set(0), 1:set(1), 2:set(1), 3:set(1,2)}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        if not stones:
            return False
        candidates = {stones[i]: set() for i in xrange(len(stones))}
        candidates[0].add(0)
        for i in xrange(len(stones)):
            if not candidates[stones[i]]:
                continue
            for j in candidates[stones[i]]:
                temp = [j+1]
                if j - 1> 0:  # 只能往终点跳
                    temp.append(j-1)
                if j > 0:  # 只能往终点跳
                    temp.append(j)
                for tt in temp:
                    if tt + stones[i] in candidates:
                        candidates[tt+stones[i]].add(tt)
        return True if candidates[stones[-1]] else False