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

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.

终于等到青蛙过河问题了，一颗赛艇。题目中说青蛙如果上一次跳了k距离，那么下一次只能跳k-1, k, 或k+1的距离，那么青蛙跳到某个石头上可能有多种跳法，由于这道题只是让我们判断青蛙是否能跳到最后一个石头上，并没有让我们返回所有的路径，这样就降低了一些难度。我们可以用递归来做，我们维护一个哈希表，建立青蛙在pos位置和拥有jump跳跃能力时是否能跳到对岸。为了能用一个变量同时表示pos和jump，我们可以将jump左移很多位并或上pos，由于题目中对于位置大小有限制，所以不会产生冲突。我们还是首先判断pos是否已经到最后一个石头了，是的话直接返回true；然后看当前这种情况是否已经出现在哈希表中，是的话直接从哈希表中取结果。如果没有，我们就遍历余下的所有石头，对于遍历到的石头，我们计算到当前石头的距离dist，如果距离小于jump-1，我们接着遍历下一块石头；如果dist大于jump+1，说明无法跳到下一块石头，m[key]赋值为false，并返回false；如果在青蛙能跳到的范围中，我们调用递归函数，以新位置i为pos，距离dist为jump，如果返回true了，我们给m[key]赋值为true，并返回true。如果结束遍历我们给m[key]赋值为false，并返回false，参加代码如下：

解法一：

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, bool> m;
        return helper(stones, 0, 0, m);
    }
    bool helper(vector<int>& stones, int pos, int jump, unordered_map<int, bool>& m) {
        int n = stones.size(), key = pos | jump << 11;
        if (pos >= n - 1) return true;
        if (m.count(key)) return m[key];
        for (int i = pos + 1; i < n; ++i) {
            int dist = stones[i] - stones[pos];
            if (dist < jump - 1) continue;
            if (dist > jump + 1) return m[key] = false;
            if (helper(stones, i, dist, m)) return m[key] = true;
        }
        return m[key] = false;
    }
};

我们也可以用迭代的方法来解，用一个哈希表来建立每个石头和在该位置上能跳的距离之间的映射，建立一个一维dp数组，其中dp[i]表示在位置为i的石头青蛙的弹跳力(只有青蛙能跳到该石头上，dp[i]才大于0)，由于题目中规定了第一个石头上青蛙跳的距离必须是1，为了跟后面的统一，我们对青蛙在第一块石头上的弹跳力初始化为0(虽然为0，但是由于题目上说青蛙最远能到其弹跳力+1的距离，所以仍然可以到达第二块石头)。我们用变量k表示当前石头，然后开始遍历剩余的石头，对于遍历到的石头i，我们来找到刚好能跳到i上的石头k，如果i和k的距离大于青蛙在k上的弹跳力+1，则说明青蛙在k上到不了i，则k自增1。我们从k遍历到i，如果青蛙能从中间某个石头上跳到i上，我们更新石头i上的弹跳力和最大弹跳力。这样当循环完成后，我们只要检查最后一个石头上青蛙的最大弹跳力是否大于0即可，参见代码如下：

解法二：

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> m;
        vector<int> dp(stones.size(), 0);
        m[0].insert(0);
        int k = 0;
        for (int i = 1; i < stones.size(); ++i) {
            while (dp[k] + 1 < stones[i] - stones[k]) ++k;
            for (int j = k; j < i; ++j) {
                int t = stones[i] - stones[j];
                if (m[j].count(t - 1) || m[j].count(t) || m[j].count(t + 1)) {
                    m[i].insert(t);
                    dp[i] = max(dp[i], t);
                }
            }
        }
        return dp.back() > 0;
    }
};

本文转自博客园Grandyang的博客，原文链接：青蛙过河[LeetCode] Frog Jump ，如需转载请自行联系原博主。