403. Frog Jump (Hard).md

403. Frog Jump (Hard)

https://leetcode.com/problems/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 < 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.

代码

• HashMap，key 为每个石头的位置 stones[0...i]，value 代表一组数字，即以当前 stones[i] 为终点时，其他地方跳到该点所有可能的步数。例如，Map.get(stones[n - 1]) 代表以最后一个石头为终点，从其他地方调到这个stones[n - 1]所需要的步数（步数集合 HashSet )
• Java 代码

class Solution {
    public boolean canCross(int[] stones) {
        if (stones.length == 0) return false;
        Map<Integer, Set<Integer>> hm = new HashMap<>();
        int n = stones.length;
        for (int i = 0; i < stones.length; i++) {
            hm.put(stones[i], new HashSet<>());
        }
        
        hm.get(0).add(0);
        
        for (int i = 0; i < stones.length; i++) {
            for (int lastStep : hm.get(stones[i])) {
                for (int x = lastStep - 1; x <= lastStep + 1; x++) {
                    if (x > 0 && hm.containsKey(stones[i] + x)) {
                        hm.get(stones[i] + x).add(x);
                    }
                }
            }
        }
        
        return !hm.get(stones[n-1]).isEmpty();
    }
}

• Python 带注释

class Solution:
    def canCross(self, A: List[int]) -> bool:     
        if len(A) == 0:    return False
        mp = {}
        for stone in A:
            mp[stone] = set()
            
        mp[0].add(0) # 第一步的上一步来源是自己，所以lastStep是0，初始化。
        for i in range(len(A)):
            for lastStep in mp[A[i]]:
                for nextStep in range(lastStep-1, lastStep+2):
                    # if unit = k, next we can jump to [k-1, k, k+1]
                    if nextStep > 0 and (A[i]+nextStep) in mp:
                        # check the direction we jump is always ahead
                        # check the next position we jump is a stone
                        mp[A[i]+nextStep].add(nextStep) # add possible nextStep
        
        # check if there is any possible step towards the last stone, return true if it's not empty.
        return True if len(mp[A[-1]]) != 0 else False