403 Frog Jump

ref: 403. Frog Jump

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 < 2^31. 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.

Company Tag: Snapchat

分析

首先想到的肯定是backtracking.但是问题就是backtracking的效率都很低。

所以一般的思路就是考虑一下，如果返回的是计数或者boolean，那么我们就考虑一下dp可不可以做。如果dp不能做的话，就往word ladder那方面想，看能不能计算每一次下面一步走，其实就是bfs那种

首先说一下自己的思路。

就是挺普通的，每一种都试一下，直到超过了stone的边界或者跳到的地方没有stone。

注意的点就是：

• 如果当前的step是1，那么下一步不可以跳0步
• 因为这个stone的大小可能超级大，所以不要用boolean[]来存该位置有没有stone，用一个set吧

代码

public boolean canCross(int[] stones) {
    if(stones.length == 0) {
        return false;
    }
    int len = stones.length;
    int n = stones[len - 1];
    Set<Integer> hasStone = new HashSet<Integer>();
    for(int i = 0; i < len; i++) {
        hasStone.add(stones[i]);
    }
    return helper(hasStone, n, 0, 0);
}

private boolean helper(Set<Integer> hasStone, int n, int curPos, int stepSize) {
    if(!hasStone.contains(curPos)) {
        return false;
    }
    if(curPos == n) {
        return true;
    }
    boolean res = false;
    if(curPos + stepSize + 1 <= n) {
        res = res || helper(hasStone, n, curPos + stepSize + 1, stepSize + 1);
    }
    if(stepSize != 0 && curPos + stepSize <= n) {
        res = res || helper(hasStone, n, curPos + stepSize, stepSize);
    }
    if(stepSize > 1 && curPos + stepSize - 1 <= n) {
        res = res || helper(hasStone, n, curPos + stepSize - 1, stepSize - 1);
    }
    return res;
}

然后别人的做法是

用一个hashmap<Integer, Set<Integer>>，key的值是存在是石头，value的意思是，由这个石头出发，可以迈出的步子的可能性。

public boolean canCross(int[] stones) {
    if(stones.length == 0 || stones[0] != 0) {
        return false;
    }
    Map<Integer, Set<Integer>> steps = new HashMap<>();
    int len = stones.length;
    for(int i = 0; i < len; i++) {
        steps.put(stones[i], new HashSet<Integer>());
    }
    Set<Integer> firstStep = steps.get(0);
    firstStep.add(1);
    steps.put(0, firstStep);
    int lastStone = stones[len - 1];
    for(int i = 0; i < len; i++) {
        int curStone = stones[i];
        for(int step: steps.get(curStone)) {
            int reach = curStone + step;
            if(reach == stones[len - 1]) {
                return true;
            }
            if(steps.containsKey(reach)) {
                Set<Integer> canReach = steps.get(reach);
                canReach.add(step);
                canReach.add(step + 1);
                if(step > 1) {
                    canReach.add(step - 1);
                }
            }
        }
    }
    return false;
}

然后就很好理解了。

按照顺序，对于每一块石头，对于它可能通过step到达的地方，

　　如果这块石头直接能到最后一块石头，就返回true

　　如果map里面包含这个可以到达的地方（此位置没有stone）

　　　　就把它可以到的地方，加上step的可能性，step - 1, step, step +1.（需要判断step > 1,不然不要加step -1 ，不需要考虑超过长度的问题，因为下一次它的位置是没有石头的）