共计 5605 个字符,预计需要花费 15 分钟才能阅读完成。
题目形容
这是 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[][]$ 作为动规数组:
- 第一维为可变参数 $u$,代表石子列表的下标,范畴为数组
stones
长度; - 第二维为可变参数 $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 多平台公布