乐趣区

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

题目形容

这是 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 多平台公布

退出移动版