LeetCode-403-Frog-Jump

jiezi

5 年前

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog’s last jump was k units, then its next jump must be either k – 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

The number of stones is ≥ 2 and is < 1,100.
Each stone’s position will be a non-negative integer < 231.
The first stone’s position is always 0.

Example 1:

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

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

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

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

请注意：

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

示例 1:

[0,1,3,5,6,8,12,17]

总共有 8 个石子。第一个石子处于序号为 0 的单元格的位置, 第二个石子处于序号为 1 的单元格的位置,
第三个石子在序号为 3 的单元格的位置，以此定义整个数组...
最后一个石子处于序号为 17 的单元格的位置。返回 true。即青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 
跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 
跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

示例 2:

[0,1,2,3,4,8,9,11]

返回 false。青蛙没有办法过河。这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划。记走到当前 stone 位置 i 的走法为 steps「type：List」；
为了走到下一个位置 j，我们遍历 steps 中的每个 step，于是我们有（step -1，step，step +1）三种向前走的走法；
我们找到三种走法中能够走到下一个位置 j 的走法，并记录从上一个位置走到 j 花的步数 step；
我们在遍历的过程中判断时候有任意一次走到了结尾位置，如果有返回 True；如果遍历完了都没有，返回 False；
以 stones 为键构建字典，键 stone，值为 List，表示从上一个位置到当前位置花费的步数；

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-09-08 08:01:56
# @Last Modified by:   何睿
# @Last Modified time: 2019-09-08 09:07:52

from typing import List


class Solution:
    def canCross(self, stones: List[int]) -> bool:
        stages = {x: set() for x in stones}
        stages[0] = {0}
        end = stones[-1]

        for key in stones:
            steps = stages[key]
            # 如果 steps 为空，说明不能到达当前位置，可以直接返回 False
            if not steps:
                return False
            # 遍历 steps 中的每一个 step，每一个 step 有三种向前走的走法
            # 如果任意一种走法达到了结尾，退出循环，返回 True
            if any(map(lambda step: self.__jump(stages, step, key, end), steps)):
                return True

        return False

    def __jump(self, stages, step, start, end):

        steps = (step - 1, step, step + 1)
        for s in filter(lambda x: x > 0 and start + x in stages, steps):
            stages[start + s].add(s)
            if start + s == end:
                return True

        return False

LeetCode-403-Frog-Jump

Description

描述

思路