fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
BFS 算法解题套路框架 :: labuladong的算法小抄
我觉得用先进先出的队列存储要遍历的节点，就是BFS；用先进后出的栈来存储即将遍历的节点就是DFS；
BFS可以用集合，需要在遍历当前层级的节点时，把下层节点存储到临时集合变量中，保证先处理当前层节点，队列本身就能做到，所以不用临时变量。
回溯法是DFS，是因为它用函数递归的方法，相当于是用函数栈存储的节点信息，转换成迭代法就是自己用个栈结构存储节点就行了；
双向BFS不只要知道目标在哪里，是不是还必须有逆向路径，比如用链表实现二叉树，知道目标是那个节点，想知道从根到它的路径，如果是双向链表，就可以从目标往根找，否则只能从根往目标找。
不知理解的对不对。
非常感谢作者，你把特殊的算法个例进行了一般化，变成了各种框架，和编程中把特例需求一般化，解决了一般化的问题就解决了所有的特列是一个道理。我能有兴趣研究算法真是多亏了你。
@tinyhare 很高兴能帮到你，你理解的很透彻，BFS 和 DFS（回溯）本质上都是暴力穷举算法，就是实现形式上的不同导致特点不同。很多算法本质都类似，所以只要能够掌握框架，算法并没有多难的，加油~
Python版本的双向bfs，ac100%
class Solution(object):
def openLock(self, deadends, target):
"""
:type deadends: List[str]
:type target: str
:rtype: int
"""
visited = set(deadends)
if '0000' in visited:
return -1
q1 = set(['0000'])
q2 = set([target])
step = 0
while q1 and q2:
tmp = set()
for curr in q1:
if curr in q2:
return step
if curr in visited:
continue
visited.add(curr)
for i in range(4):
for d in (-1, 1):
next = curr[:i] + str((int(curr[i]) + d) % 10) + curr[i + 1:]
tmp.add(next)
step += 1
q1 = q2
q2 = tmp
return -1
@yzw-Joey 代码中temp保存的是下一轮的所有节点，visited只保存了当前轮的所有节点，所以temp转为q2，q2里面的节点并没有存入visited中，判断q1和q2是否有交集是可行的。
@yzw-Joey
之前的案例是在stack.push(object) 的时候加入visited里，所以任何已经访问过和即将被访问的元素都在里面。
Double BFS的代码里是在stack.pop(object)的时候才加入visited里，只有已经访问过的元素在里面。而q1和q2里面的元素都属于即将被访问。
这两个加入visited的不同时机并不影响结果，算是博主代码风格的不统一吧。
可以不需要 dead 这个哈希集合，可以直接将这些元素初始化到 visited 集合中，效果是一样的，可能更加优雅一些。
合并后的代码如下：
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> visited = new HashSet<>();
for(String s:deadends) visited.add(s);
Queue<String> q = new LinkedList<>();
int res = 0;
q.offer("0000");
while(!q.isEmpty()){
int sz = q.size();
for(int i=0; i<sz; i++){
String cur = q.poll();
if(visited.contains(cur)){
continue;
}else{
visited.add(cur);
}
if(target.equals(cur)) return res;
for(int j=0; j<4; j++){
String up = plusOne(cur,j);
if(!visited.contains(up)) q.offer(up);
String down = minusOne(cur,j);
if(!visited.contains(down)) q.offer(down);
}
}
res++;
}
return -1;
}
private String plusOne(String s, int i){
char[] c = s.toCharArray();
if(c[i]=='9') c[i] = '0';
else c[i]++;
return new String(c);
}
private String minusOne(String s, int i){
char[] c = s.toCharArray();
if(c[i]=='0') c[i] = '9';
else c[i]--;
return new String(c);
}
}
请问对于从queue里移除元素的q.poll(), q.remove()和在queue里加元素的q.offer(), q.add()的选择对于BFS来说有什么讲究吗。我看模版里用的是q.poll()和q.offer(),是另一个组用法有什么地方不好吗，还是两种用法在BFS的题里没有区别。谢谢了 :D
@YANLING-H 对于面试没区别，工业上会有应用。.add()来自Collection<E>，而offer来自Queue<E>。
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add(E), which can fail to insert an element only by throwing an exception.
class Solution { public: string plusOne(string cur, int i) { if (cur[i] == '9') { cur[i] = '0'; } else { cur[i] += 1; } return cur; }
string minusOne(string cur, int i) {
if (cur[i] == '0') {
cur[i] = '9';
}
else {
cur[i] -= 1;
}
return cur;
}
int openLock(vector<string>& deadends, string target) {
queue<string> que;
set<string> visited;
int step = 0;
que.push("0000");
visited.insert("0000");
while (!que.empty()) {
int n = que.size();
cout << n << endl;
for (int k = 0; k < n; ++k) {
string cur = que.front();
que.pop();
// dead
if (find(deadends.begin(), deadends.end(), cur) != deadends.end()) {
continue;
}
if (target == cur)
return step;
for (int i = 0; i < 4; ++i) {
string up = plusOne(cur, i);
if (find(visited.begin(), visited.end(), up) == visited.end()) {
que.push(up);
visited.insert(up);
}
string down = minusOne(cur, i);
if (find(visited.begin(), visited.end(), down) == visited.end()) {
que.push(down);
visited.insert(down);
}
}
}
++step;
}
return -1;
}
}; 请问这个c++代码有什么问题吗，过不了例子3： ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
js 版二叉树最小高度
function minDepth(root) {
if (root == null) return 0;
const q = [];
q.push(root);
// root 本身就是一层，depth 初始化为 1
let depth = 1;
while (q.length) {
const len = q.length;
/* 将当前队列中的所有节点向四周扩散 */
for (let i = 0; i < len; i++) {
const cur = q.shift();
/* 判断是否到达终点 */
if (cur.left == null && cur.right == null) return depth;
/* 将 cur 的相邻节点加入队列 */
if (cur.left !== null) q.push(cur.left);
if (cur.right !== null) q.push(cur.right);
}
/* 这里增加步数 */
depth++;
}
return depth;
}
js 版开锁次数
var openLock = function(deadends, target) {
// 将 s[j] 向上拨动一次
function plusOne(s, j) {
let replacement = s[j] === "9" ? 0 : parseInt(s[j]) + 1;
return s.substr(0, j) + replacement + s.substr(j + 1);
}
// 将 s[j] 向下拨动一次
function minusOne(s, j) {
let replacement = s[j] === "0" ? 9 : parseInt(s[j]) - 1;
return s.substr(0, j) + replacement + s.substr(j + 1);
}
// BFS 框架，打印出所有可能的密码
function BFS() {
// 记录已经穷举过的密码，防止走回头路
const visited = {
"0000": true,
};
// 从起点开始启动广度优先搜索
const q = ["0000"];
let step = 0;
while (q.length) {
const len = q.length;
/* 将当前队列中的所有节点向周围扩散 */
for (i = 0; i < len; i++) {
const cur = q.shift();
/* 判断死亡数字 */
if (deadends.includes(cur)) continue;
/* 判断是否到达终点 */
if (cur === target) return step;
/* 将一个节点的相邻节点加入队列 */
for (j = 0; j < 4; j++) {
up = plusOne(cur, j);
if (visited[up] === undefined) {
q.push(up);
visited[up] = true;
}
down = minusOne(cur, j);
if (visited[down] === undefined) {
q.push(down);
visited[down] = true;
}
}
}
/* 在这里增加步数 */
step++;
}
return -1;
}
return BFS();
};
使用PHP解题时遇到的坑：判断当前节点是否存在于visited和deadends时一开始使用的是in_array函数，这样会拖慢速度，后来看到大佬的题解，将visited和deadends存成map，然后判断当前节点作为map的键是否存在相应的值
PHP代码：
class Solution {
/**
* @param String[] $deadends
* @param String $target
* @return Integer
*/
function openLock($deadends, $target) {
$queue = array();
$visit = array();
foreach($deadends as $deadend){
$deadMap[$deadend] = 1;
}
array_push($queue, '0000');
array_push($visit, '0000');
$step = 0;
while(!empty($queue)){
$sz = count($queue);
for($i = 0; $i < $sz; $i++){
$cur = array_shift($queue);
if($cur == $target) return $step;
if(isset($deadMap[$cur])) continue;
for($j = 0; $j < 4; $j++){
$temp = $this->up($cur, $j);
if(!isset($visit[$temp])){
array_push($queue, $temp);
$visit[$temp] = 1;
}
$temp = $this->down($cur, $j);
if(!isset($visit[$temp])){
array_push($queue, $temp);
$visit[$temp] = 1;
}
}
}
$step++;
}
return -1;
}
function up($cur, $j){
if($cur[$j] == '9'){
$cur[$j] = '0';
}else{
$cur[$j] = $cur[$j] + 1;
}
return $cur;
}
function down($cur, $j){
if($cur[$j] == '0'){
$cur[$j] = '9';
}else{
$cur[$j] = $cur[$j] - 1;
}
return $cur;
}
}
我之前用这个代码 把deadends直接加到visited里面之后，其他逻辑好像跟您提供的一样，但没有办法catch到我说的edge case
class Solution {
public int openLock(String[] deadends, String target) {
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
for(String dead:deadends){
visited.add(dead);
}
q.offer("0000");
visited.add("0000");
int step = 0;
while(!q.isEmpty()){
int sz = q.size();
for(int i =0;i<sz; i++){
String cur = q.poll();
// visited.add(cur);
if(cur.equals(target)) return step;
else {
for(int index=0;index<4;index++){
String up = turnUp(cur,index);
System.out.println(up);
String down = turnDown(cur,index);
System.out.println(down);
if(!visited.contains(up)){
q.offer(up);
visited.add(up);
}
if(!visited.contains(down)){
q.offer(down);
visited.add(down);
}
}
}
}
step++;
}
return -1;
}
private String turnUp(String str, int index){
char[] ch = str.toCharArray();
if(ch[index]=='9') ch[index]='0';
else ch[index] += 1;
return String.copyValueOf(ch);
}
private String turnDown(String str, int index){
char[] ch = str.toCharArray();
if(ch[index]=='0') ch[index]='9';
else ch[index] -= 1;
return String.copyValueOf(ch);
}
}
@WeibinZ 因为我的代码单独处理了 deadends 集合，所以这段代码可以正确处理你说的这种情况：
if (deads.contains(cur))
continue;
你合并了 deadends 和 visited 集合，确实需要额外处理一下这个 base case。
"可以不需要 dead 这个哈希集合，可以直接将这些元素初始化到 visited 集合中，效果是一样的" 这样不行吧，因为dead是在第一层for循环判断的，visited是在第二层判断的。这样当我deads是["0000"]时，queue中第一个元素"0000"就没法被dead拦截。
C++版本(注意unorded_map中判定是否存在)
int openLock(vector<string>& deadends, string target) { //BFS广度优先遍历
queue<string> node;
unordered_set<string> dead;
unordered_set<string> visited;
for(auto s:deadends){
dead.insert(s);
}
int step = 0;
node.push("0000");
visited.insert("0000");
while(!node.empty()){
int size = node.size();
for(int i=0;i<size;i++){
string cur = node.front();
node.pop();
if(dead.find(cur)!=dead.end()) continue;
if(cur == target) return step;
for(int j = 0;j<4;j++){
string up = plusOne(cur, j);
if (!visited.count(up)) {
node.push(up);
visited.insert(up);
}
string down = minusOne(cur, j);
if (!visited.count(down)) {
node.push(down);
visited.insert(down);
}
}
}
step++;
}
return -1;
}
};
@Goolloo
之前的案例是在stack.push(object) 的时候加入visited里，所以任何已经访问过和即将被访问的元素都在里面。 Double BFS的代码里是在stack.pop(object)的时候才加入visited里，只有已经访问过的元素在里面。而q1和q2里面的元素都属于即将被访问。这两个加入visited的不同时机并不影响结果，算是博主代码风格的不统一吧。
如果是pop()才加入visited，有没有可能同一层有重复节点？这两种风格还是有一点点区别的吧。如果是push()就visited，我双向bfs会出现q1 q2无交集找不到路径的情况。
我在写教程时肯定会考虑风格统一，最好抽象成模板，这是我的一贯原则。但具体的问题中细节甚多，我的写法是尝试了各种写法之后给出的理解成本最低的写法。希望大家多动手实践自己的想法，然后就可以把思路内化于心，收发自如，而不是拘泥于框架形式了。
