leetcode BFS解题思路
2024-08-23 02:00:51
Word Ladder
思路一:单向bfs, 使用visited数组记录哪些已经访问过了, 访问过的就不允许再次入队, 同时这里想到的是使用26个英文字母，枚举可能的取值, 类似brute force
思路二:双向bfs，使用两个set，这里没有使用queue，是因为需要在queue里查询，不方便.
另外，需要注意的一点是，每次遍历时，都是取size较小的来做搜索，初始时，各插入头和尾，之后每次取最小的set来拓展， 这样就实现了交替访问两个set,
是两者的高度在 l/2, 这样可以缩短一般的时间单词接龙 II
思路一：因为要存储最终的结果，所以图是一定要建立的，通常我们可以通过维护每个节点的子节点，即一个map，每个map里是一个数组
我们可以称之为children数组活着parent数组
2）每遍历一层节点后，从wordlist中删除掉这些节点，因为本题是有源节点的，从源节点看，前一层的节点不应该再次呗遍历，因为长度变长了
3）对于重复的问题，可以使用hastset来解决
4）最后通过dfs，遍历输出结果
思路二：双向bfs + dfs
解法跟思路一类似，只是需要创建两个set，然后需要不断交换两个set
- Race Car
思路一：bfs解法有一个重要的技巧，即利用一个set，记录已经出现过的路径，这样bfs枚举到重复路径时，可以直接跳过，这是一个有效的prunning method.
最新文章
- 第7章 权限管理（1）_ACL权限
- JavaWeb学习笔记——表达式语言
- [原]SyntaxHighlighter使用笔记
- Java——String.split()函数
- bzoj2257
- bootstrap学习笔记--bootstrap网格系统
- POJ3274 hash
- poj3708：函数式化简+高精度进制转换+同余方程组
- VBS脚本合集（自制脚本）
- TP5.0实现无限极回复功能
- [实例]JAVA生成字母+随机数字并生成文件
- 华盛顿邮报：FBI 屡次夸大了“手机加密威胁”的数字
- Hper-V卸载
- connect socket的超时设置
- 某公司的U3D笔试题
- ORA-12541：TNS:无监听程序 解决办法
- js的小知识7
- 自己总结的C#编码规范--前言&目录
- 简单记录下3PC
- Codeforces Round #503 Div1+Div2 1019&1020