403. Frog Jump

week7

难度：Hard

题目链接

题目描述

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.

Example1:

[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.

Example2:

[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.

题目分析

  著名的青蛙跳石头问题，在大一的时候一次ACM比赛中碰到一次，貌似是原题，结果很显然扑街了，现在看到题目才算正式理解了题目。。。想来当时没有学习什么数据结构也是做不出的了，暴力AK明显会timelimit。
  青蛙跳石头的题意是有一只青蛙要过河，河流分成X个部分，有的地方有石头，有的没有。而这只青蛙要连续跳过去，可能这只青蛙的手刹有点毛病，每当跳过K个单位时，下一次跳越要是K-1、K或者K+1个单位，并且只能向前。
  一开始的理解是只要判断下一块石头是否在跳越范围内就行了，但注意的是青蛙可以飞过某一块石头，所以就有很多种跳越方式，假设有两条路径能到达点A，通过不同路径后到达点A后，其下一步的跳越范围（能力）也会不一样，所以情况会很复杂。

第一次解题思路

  由于青蛙的选择路径的多变，会引起后续的跳越，因此它的选择分支是从第一次就开始了，试想一下每个分支又会衍生不同的分支，那不就是一颗路径树了吗，只要遍历这一棵树，找到某一路径可以到达终点即可，因为只需要得出青蛙是否能过河的结论，所以无需遍历所有路径（除非所有路径都不能到达）。
  为了尽快地解决问题，很明显是用深度遍历的，当得到一条路径后，马上返回true节省时间。所以使用递归的方式，遍历所有状态。

代码

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
31
32
33
#include<vector>
#include<iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
    bool canCross(vector<int>& stones) {
        stoness = stones;
        return cross(stoness.begin(),0);
    }

    bool cross(vector<int>::iterator start, int dis) {
        if(start == stoness.end()-1)
        {
            return true;
        }
        for(int i = dis - 1; i <= dis+1; i++)
        {
            vector<int>::iterator it = find(start+1,stoness.end(),i+*start);
            if(it != stoness.end()){
                if(cross(it,i)) {
                    return true;
                }
            } else {
                continue;
            }
        }
        return false;
    }

private:
    vector<int>stoness;
};

结果与反思

  在过了example后，提交的检测超时了，例子是[1…998,99999999],这个极端的例子展示了这个算法的弱点，没有根据搜索得的信息加快速度，每次都搜索到了998这个节点，但由于最后一个点不可到达，所以都在最后一步终止，浪费了大量的时间，所以我们要采取一种措施及时止损。

第二次解题思路

  采用遍历路径树是没有错的，因为我们需要验证每一条路径是否能通往最后一个节点，但我们不能重复判断同一个状态多次，因为每条路径中有着许多相同的状态，即达到点相同，且下一步的跳越范围相同，如果我们在一条路径中已经得知该状态是否能达到终点，就可以在其它路径中引用进行快速判断。就是如一个节点不通，则经过该节点的所有路径都不通。

  具体方法是维护一个哈希表保存状态的可行性，因为一个状态有两个属性，一是点的位置，二是上一步跳越距离，因为石头数量有限，可以通过左移取或，将两个值合并起来得到一个唯一的值，从而确定一个唯一的状态，保存该状态是否能达到终点。

改进代码

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
31
32
33
34
35
36
37
38
39
#include<vector>
#include<iostream>
#include <algorithm>
#include<unordered_map>
using namespace std;
class Solution {
public:
    bool canCross(vector<int>& stones) {
        stoness = stones;
        return cross(stoness.begin(),0);
    }

    bool cross(vector<int>::iterator start, int dis) {
        if(start == stoness.end()-1)
        {
            return true;
        }
        int key = *start | dis<<11;
        if (status.count(key)) {
            return status[key];
        }
        for(int i = dis + 1; i >= dis-1; i--)
        {
            vector<int>::iterator it = find(start+1,stoness.end(),i+*start);
            if(it != stoness.end()){
                if(cross(it,i)) {
                    return status[key] = true;
                }
            } else {
                continue;
            }
        }
        return status[key] = false;;
    }

private:
    vector<int>stoness;
    unordered_map<int, bool> status;
};

Note

  1. 在查询下一个跳越点时，可以使用循环来寻找，但我觉得如果跳越距离很大，那么就要遍历很多个位置，因此使用find直接在vector中寻找对应k-1，k，k+1距离的点会更加快。

  2. 在看了一下别人的做法中，发现可以先在两个点之后，判断是否后一个点是前一个点的两倍还多，即stone[i]>2*stone[i-1]，若存在这一情况，那么必定不能到达，因为青蛙在2次跳越后，不可能跳越2倍的距离，而且这个数组又是升序的，所以不可逾越。可以去掉很多极端情况。

  3. 看了一下题目的评论，有一个评论说从步数大的开始遍历会更快得到答案，想了一下似乎是这样的，因位较小的步数最终很有可能走到大步数的状态，中间多出了很多不必要的状态，改成i–后，从24ms提升到了16ms，感觉改善很客观。居然能到95.46%了。

Frog Jump_test
Frog Jump_test

总结

  这个题目的关键之处在于如何利用已知的信息进行搜索，而不是采用盲目搜索的方式，在搜索过程中，发现一个点不通则将之后的路径封掉，对信息的复用，极大加快算法的速度，另外一些顺序的选择也很有可能影响速度。