乐趣区

关于后端:面试高频题从爆搜到记忆化搜索到动态规划

jiezi

题目形容

这是 LeetCode 上的 403. 青蛙过河 ，难度为 艰难。

Tag :「DFS」、「BFS」、「记忆化搜寻」、「线性 DP」

一只青蛙想要过河。假设河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。青蛙能够跳上石子，然而不能够跳入水中。

给你石子的地位列表 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] <= 2^{31} – 1$
  • $stones[0] = 0$

DFS（TLE）

依据题意，咱们能够应用 DFS 来模仿 / 爆搜一遍，查看所有的可能性中是否有能达到最初一块石子的。

通常设计 DFS 函数时，咱们只须要不失一般性的思考实现第 $i$ 块石子的跳跃须要些什么信息即可：

  • 须要晓得以后所在位置在哪，也就是须要晓得以后石子所在列表中的下标 $u$。
  • 须要晓得以后所在位置是通过多少步而来的，也就是须要晓得上一步的跳跃步长 $k$。

代码：

class Solution {Map<Integer, Integer> map = new HashMap<>();
    public boolean canCross(int[] ss) {
        int n = ss.length;
        // 将石子信息存入哈希表
        // 为了疾速判断是否存在某块石子，以及疾速查找某块石子所在下标
        for (int i = 0; i < n; i++) {map.put(ss[i], i);
        }
        // check first step
        // 依据题意，第一步是固定通过步长 1 达到第一块石子（下标为 1）if (!map.containsKey(1)) return false;
        return dfs(ss, ss.length, 1, 1);
    }

    /**
     * 断定是否可能跳到最初一块石子
     * @param ss 石子列表【不变】* @param n  石子列表长度【不变】* @param u  以后所在的石子的下标
     * @param k  上一次是通过多少步跳到以后地位的
     * @return 是否能跳到最初一块石子
     */
    boolean dfs(int[] ss, int n, int u, int k) {if (u == n - 1) return true;
        for (int i = -1; i <= 1; i++) {
            // 如果是原地踏步的话，间接跳过
            if (k + i == 0) continue;
            // 下一步的石子实践编号
            int next = ss[u] + k + i;
            // 如果存在下一步的石子，则跳转到下一步石子，并 DFS 上来
            if (map.containsKey(next)) {boolean cur = dfs(ss, n, map.get(next), k + i);
                if (cur) return true;
            }
        }
        return false;
    }
}
  • 工夫复杂度：$O(3^n)$
  • 空间复杂度：$O(3^n)$

但数据范畴为 $10^3$，间接应用 DFS 必定会超时。

咱们须要思考退出「记忆化」性能，或者改为应用带标记的 BFS。

记忆化搜寻

在思考退出「记忆化」时，咱们只须要将 DFS 办法签名中的【可变】参数作为维度，DFS 办法中的返回值作为存储值即可。

通常咱们会应用「数组」来作为咱们缓存两头后果的容器，

对应到本题，就是须要一个 boolean[石子列表下标][跳跃步数] 这样的数组，但应用布尔数组作为记忆化容器往往无奈辨别「状态尚未计算」和「状态曾经计算，并且后果为 false」两种状况。

因而咱们须要转为应用 int[石子列表下标][跳跃步数]，默认值 $0$ 代表状态尚未计算，$-1$ 代表计算状态为 false，$1$ 代表计算状态为 true。

接下来须要估算数组的容量，能够从「数据范畴」动手剖析。

依据 2 <= stones.length <= 2000，咱们能够确定第一维（数组下标）的长度为 $2009$，而另外一维（跳跃步数）是与跳转过程相干的，无奈间接确定一个准确边界，然而一个不言而喻的事实是，跳到最初一块石子之后的地位是没有意义的，因而咱们不会有「跳跃步长」大于「石子列表长度」的状况，因而也能够定为 $2009$（这里是利用了由下标为 $i$ 的地位发动的跳跃不会超过 $i + 1$ 的性质）。

至此，咱们定下来了记忆化容器为 int[][] cache = new int[2009][2009]。

然而能够看出，上述确定容器大小的过程还是须要一点点剖析 & 教训的。

那么是否有思维难度再低点的办法呢？

答案是有的，间接应用「哈希表」作为记忆化容器。「哈希表」自身属于非定长容器汇合，咱们不须要剖析两个维度的下限到底是多少。

另外，当容器维度较多且上界较大时（例如上述的 int[2009][2009]），间接应用「哈希表」能够无效升高「爆空间 / 工夫」的危险（不须要每跑一个样例都创立一个百万级的数组）。

代码：

class Solution {Map<Integer, Integer> map = new HashMap<>();
    // int[][] cache = new int[2009][2009];
    Map<String, Boolean> cache = new HashMap<>();
    public boolean canCross(int[] ss) {
        int n = ss.length;
        for (int i = 0; i < n; i++) {map.put(ss[i], i);
        }
        // check first step
        if (!map.containsKey(1)) return false;
        return dfs(ss, ss.length, 1, 1);
    }
    boolean dfs(int[] ss, int n, int u, int k) {
        String key = u + "_" + k;
        // if (cache[u][k] != 0) return cache[u][k] == 1;
        if (cache.containsKey(key)) return cache.get(key);
        if (u == n - 1) return true;
        for (int i = -1; i <= 1; i++) {if (k + i == 0) continue;
            int next = ss[u] + k + i;
            if (map.containsKey(next)) {boolean cur = dfs(ss, n, map.get(next), k + i);
                // cache[u][k] = cur ? 1 : -1;
                cache.put(key, cur);
                if (cur) return true;
            }
        }
        // cache[u][k] = -1;
        cache.put(key, false);
        return false;
    }
}
  • 工夫复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

动静布局

有了「记忆化搜寻」的根底，要写写进去动静布局就变得绝对简略了。

咱们能够从 DFS 函数登程，写出「动静布局」解法。

咱们的 DFS 函数签名为：

boolean dfs(int[] ss, int n, int u, int k);

其中前两个参数为不变参数，后两个为可变参数，返回值是咱们的答案。

因而能够设定为 $f[][]$ 作为动规数组：

  1. 第一维为可变参数 $u$，代表石子列表的下标，范畴为数组 stones 长度；
  2. 第二维为可变参数 $k$，代表上一步的的跳跃步长，后面也剖析过了，最多不超过数组 stones 长度。

这样的「状态定义」所代表的含意：以后在第 $i$ 个地位，并且是以步长 $k$ 跳到地位 $i$ 时，是否达到最初一块石子。

那么对于 $f[i][k]$ 是否为真，则取决于上一地位 $j$ 的状态值，联合每次步长的变动为 [-1,0,1] 可知：

  • 可从 $f[j][k – 1]$ 状态而来：先是通过 $k – 1$ 的跳跃达到地位 $j$，再在原步长的根底上 +1，跳到了地位 $i$。
  • 可从 $f[j][k]$ 状态而来：先是通过 $k$ 的跳跃达到地位 $j$，维持原步长不变，跳到了地位 $i$。
  • 可从 $f[j][k + 1]$ 状态而来：先是通过 $k + 1$ 的跳跃达到地位 $j$，再在原步长的根底上 -1，跳到了地位 $i$。

只有上述三种状况其中一种为真，则 $f[i][j]$ 为真。

至此，咱们解决了动静布局的「状态定义」&「状态转移方程」局部。

但这就完结了吗？还没有。

咱们还短少可让状态递推上来的「有效值」，或者说短少初始化环节。

因为咱们的 $f[i][k]$ 依赖于之前的状态进行“或运算”而来，转移方程自身不会产生 $true$ 值。因而为了让整个「递推」过程可滚动，咱们须要先有一个为 $true$ 的状态值。

这时候再回看咱们的状态定义：以后在第 $i$ 个地位，并且是以步长 $k$ 跳到地位 $i$ 时，是否达到最初一块石子。

显然，咱们当时是不可能晓得通过「多大的步长」跳到「哪些地位」，最终能够达到最初一块石子。

这时候须要利用「对偶性」将跳跃过程「翻转」过去剖析：

咱们晓得起始状态是「通过步长为 1」的跳跃达到「地位 1」，如果从起始状态登程，存在一种计划达到最初一块石子的话，那么必然存在一条反向门路，它是以从「最初一块石子」开始，并以「某个步长 $k$」开始跳跃，最终以回到地位 1。

因而咱们能够设 $f[1][1] = true$，作为咱们的起始值。

这里实质是利用「门路可逆」的性质，将问题进行了「等效对偶」。外表上咱们是进行「正向递推」，但事实上咱们是在验证是否存在某条「反向门路」达到地位 $1$。

倡议大家增强了解 ~

代码：

class Solution {public boolean canCross(int[] ss) {
        int n = ss.length;
        // check first step
        if (ss[1] != 1) return false;
        boolean[][] f = new boolean[n + 1][n + 1];
        f[1][1] = true;
        for (int i = 2; i < n; i++) {for (int j = 1; j < i; j++) {int k = ss[i] - ss[j];
                // 咱们晓得从地位 j 到地位 i 是须要步长为 k 的跳跃

                // 而从地位 j 发动的跳跃最多不超过 j + 1
                // 因为每次跳跃，下标至多减少 1，而步长最多减少 1 
                if (k <= j + 1) {f[i][k] = f[j][k - 1] || f[j][k] || f[j][k + 1];
                }
            }
        }
        for (int i = 1; i < n; i++) {if (f[n - 1][i]) return true;
        }
        return false;
    }
}
  • 工夫复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

BFS

事实上，后面咱们也说到，解决超时 DFS 问题，除了减少「记忆化」性能以外，还能应用带标记的 BFS。

因为两者都能解决 DFS 的超时起因：大量的反复计算。

但为了「记忆化搜寻」&「动静布局」可能更好的连接，所以我把 BFS 放到最初。

如果你可能看到这里，那么这里的 BFS 应该看起来会绝对轻松。

它更多是作为「记忆化搜寻」的另外一种实现模式。

代码：

class Solution {Map<Integer, Integer> map = new HashMap<>();
    public boolean canCross(int[] ss) {
        int n = ss.length;
        for (int i = 0; i < n; i++) {map.put(ss[i], i);
        }
        // check first step
        if (!map.containsKey(1)) return false;

        boolean[][] vis = new boolean[n][n];
        Deque<int[]> d = new ArrayDeque<>();
        vis[1][1] = true;
        d.addLast(new int[]{1, 1});

        while (!d.isEmpty()) {int[] poll = d.pollFirst();
            int idx = poll[0], k = poll[1];
            if (idx == n - 1) return true;
            for (int i = -1; i <= 1; i++) {if (k + i == 0) continue;
                int next = ss[idx] + k + i;
                if (map.containsKey(next)) {int nIdx = map.get(next), nK = k + i;
                    if (nIdx == n - 1) return true;
                    if (!vis[nIdx][nK]) {vis[nIdx][nK] = true;
                        d.addLast(new int[]{nIdx, nK});
                    }
                }
            }
        }

        return false;
    }
}
  • 工夫复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.403 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版