没有合适的资源?快使用搜索试试~ 我知道了~
首页宫水三叶的图论BFS刷题策略与LeetCode127题详解
宫水三叶的刷题日记专注于图论领域的学习和实战练习,特别是Breadth-First Search (BFS)算法的应用。该专题合集是针对LeetCode平台的题库,以帮助读者提升算法技能,特别是对于初学者和进阶者来说,提供了一个系统的学习路径。 在使用这个合集时,最佳实践包括以下几个步骤: 1. 定位资源:首先,访问宫水三叶的公众号或GitHub/Gitee版本的在线目录,以便获取最新的题库更新,更新频率大约为每2-4周一次。 2. 筛选题目:在侧边栏的分类中找到“图论BFS”板块,根据题目推荐指数从高到低排序,若推荐指数相同,则按照难度由易至难选择挑战。 3. 刷题顺序:按照合集的编排顺序,即从上到下逐题学习,这样可以确保逐步建立对BFS算法的理解和应用能力。 4. 实践与反馈:在刷题过程中,遇到问题可以在「每日一题打卡QQ群」703311589中寻求帮助,与其他学习者交流,共同进步。 以LeetCode上的127题“单词接龙”为例,这是一道考察双向BFS的难题,要求找到从beginWord到endWord的最短转换序列,每次转换仅允许改变一个字母,并且中间单词必须在给定的字典wordList中。解决这类问题时,BFS的广度优先搜索策略可以有效地探索所有可能的转换路径,直到找到目标单词或者确定无法达到。 通过这个刷题日记,读者不仅能掌握BFS的基本原理,还能通过实际操作提高编程能力和解题技巧,适合那些希望通过刷题提升图论知识和算法理解的人。同时,关注公众号和社交媒体可以获取更多额外的学习资源和动态。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/86274704/bgd.jpg)
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 肯定会超时。
![](https://csdnimg.cn/release/download_crawler_static/86274704/bge.jpg)
我我们们需要考需要考虑虑加入「加入「记忆记忆化」功能,或者改化」功能,或者改为为使用使用带标记带标记的的 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] ),直接使用「哈希表」),直接使用「哈希表」
可以有效降低「爆空间可以有效降低「爆空间/时间」的风险(不需要每跑一个样例都时间」的风险(不需要每跑一个样例都创创建一个百万建一个百万级级的数的数组组)。)。
代码:
![](https://csdnimg.cn/release/download_crawler_static/86274704/bgf.jpg)
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 函数出发,写出「动函数出发,写出「动态规态规划」解法。划」解法。
剩余73页未读,继续阅读
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/d974aaab81c1462a84a8258105b8adb2_weixin_35815036.jpg!1)
魏水华
- 粉丝: 17
- 资源: 282
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Lombok 快速入门与注解详解
- SpringSecurity实战:声明式安全控制框架解析
- XML基础教程:从数据传输到存储解析
- Matlab实现图像空间平移与镜像变换示例
- Python流程控制与运算符详解
- Python基础:类型转换与循环语句
- 辰科CD-6024-4控制器说明书:LED亮度调节与触发功能解析
- AE particular插件全面解析:英汉对照与关键参数
- Shell脚本实践:创建tar包、字符串累加与简易运算器
- TMS320F28335:浮点处理器与ADC详解
- 互联网基础与结构解析:从ARPANET到多层次ISP
- Redhat系统中构建与Windows共享的Samba服务器实战
- microPython编程指南:从入门到实践
- 数据结构实验:顺序构建并遍历链表
- NVIDIA TX2系统安装与恢复指南
- C语言实现贪吃蛇游戏基础代码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)