【Day03】403.青蛙过河

403. 青蛙过河

题目描述:

一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。

给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。

开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2 )。

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

示例 1:

输入:stones = [0,1,3,5,6,8,12,17]
输出:true
解释:青蛙可以成功过河,按照如下方案跳跃:跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后,跳 5 个单位到第 8 个石子(即最后一块石子)。

示例 2:

输入:stones = [0,1,2,3,4,8,9,11]
输出:false
解释:这是因为第 5 和第 6 个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。

提示:

  • 2 <= stones.length <= 2000
  • 0 <= stones[i] <= 231 - 1
  • stones[0] == 0

题解:

递归:

class Solution {
public:
    unordered_map um;
    bool canCross(vector& stones) {

        for (int i = 0; i < stones.size(); i++) {
            um[stones[i]] = i;  // key:石子值 value是第几块石子
        }
        if (!um.count(1)) return false;
        return dfs(stones, stones.size(), 1, 1);
    }
    bool dfs(vector& stones, int n, int cur, int k) {
        if (cur == n - 1) return true;
        for (int i = -1; i <= 1; i++) {
            if (k + i == 0) continue;
            int next = stones[cur] + k + i;
            if (um.count(next)) { // 存在
                bool choose = dfs(stones, n, um[next], k + i);
                if (choose) return true;
            }
        }
        return false;
    }

};

dfs记忆化搜索:

class Solution {
public:
    unordered_map um;
    vector> memo;
    bool canCross(vector& stones) {

        for (int i = 0; i < stones.size(); i++) {
            um[stones[i]] = i;  // key:石子值 value是第几块石子
        }
        if (!um.count(1)) return false;
        memo = vector>(stones.size(), vector(stones.size(), -1));
        return dfs(stones, stones.size(), 1, 1);
    }
    bool dfs(vector& stones, int n, int cur, int k) {
        if (memo[cur][k] != -1) return memo[cur][k];
        if (cur == n - 1) return memo[cur][k] = true;
        for (int i = -1; i <= 1; i++) {
            if (k + i == 0) continue;  // 原地跳过
            int next = stones[cur] + k + i;
            if (um.count(next)) { // 存在
                bool choose = dfs(stones, n, um[next], k + i);
                if (choose) return memo[cur][k] = true;
            }
        }
        return memo[cur][k] = false;
    }

};

动态规划:

class Solution {
public:
    bool canCross(vector& stones) {
        int n = stones.size();
        if (stones[1] != 1) return false;
        vector> dp(n, vector(n));
        // dp[i][k] 表示在第i个位置且跳k个单位到第i块石子。
        dp[1][1] = true;
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                int k = stones[i] - stones[j];
                if (k > j + 1) continue;
                // 因为题目要求 青蛙第一次只能跳1步,那么第二次至多跳2步,以此类推,青蛙在第i块(i从0开始)石头上至多只能跳i+1步。在第j块石头上至多只能跳 j+1 步 ,如果k > j+1,说明石头 i 隔石头 j 太远了,远到不满足题目的隐藏规则,所以青蛙必定跳不过去。
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k+1];
            }
        }
        for (int i = 1; i < n; i++) {
            if (dp[n-1][i]) return true;
        }        
        return false;
    }
};

另一种动态规划:

class Solution {
public:
    bool canCross(vector& stones) {
        // dp[i][j] 表示 第 i 个石头是否可以跳 j 步
        int n = stones.size();
        vector> dp(n, vector(n));
        dp[0][1] = true;
        for (int i = 1; i < n; i++) {
            bool flag = false;
            for (int j = i - 1; j >= 0; j--) {
                int k = stones[i] - stones[j];
                if (k > i) break;
                if (dp[j][k]) {
                    dp[i][k - 1] = dp[i][k] = dp[i][k + 1] = true;
                    flag = true;
                }
            }
            if (i == n - 1 && !flag) {
                return false;
            }
        }
        return true;
    }
};

   转载规则


《【Day03】403.青蛙过河》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day04】137.只出现一次的数字II 【Day04】137.只出现一次的数字II
137. 只出现一次的数字 II给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 示例1: 输入:nums = [2,2,3,2] 输出:3示例2: 输入:nu
2021-04-30
下一篇 
【Day02】633.平方数之和 【Day02】633.平方数之和
题目: 给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c 。 示例 1: 输入:c = 5 输出:true 解释:1 * 1 + 2 * 2 = 5示例 2: 输入:c = 3 输出:false示例
2021-04-28
  目录