题目：
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以*旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1
本题为BFS的经典样板题，在labuladong算法书中出现在BFS算法套路框架一章中，其中包含基本BFS思路和双向BFS以及最后的小优化，作为小白选手看完后觉得甚是精妙，遂动手重复学习了一下，写完后在测试样例那里反复摩擦了很久都过不了，苦思冥想了许久甚至和源码进行了手动对比都看不出问题出在哪，一度怀疑是书的问题，甚至去下了份东哥的源码，对比了一下还是没发现问题在哪。由于折腾了大半个下午，而且这题双向BFS的思路还是挺经典的，遂将此题记录一下，顺便作为本菜鸡的第一篇博客。
首先说一下本题思路：已知这个密码锁我们每一步都只能扭动其中一位数字一次，所以每个状态下这个锁有2*4=8种变化情况，带入BFS的思想就是每一层树层有8个分支结点，将这8种新状态加入队列，然后再进行下一层搜索，如果本层搜索到密码则算法结束。需要注意的是，本题存在一个死亡名单，在宽搜的过程中我们需要对名单中的数字进行剪枝，这里引入一个visited队列进行记录，每次判断是否查找到答案的时候就进行一次剪枝判断。关于8个结点的替换，这里先把字符串通过toCharArray转换为字符数组，依据8种不同情况进行字符替换后再new一个新string返回（这里特殊处理一下 9进位到0 和 0减到9）。
思路不复杂，直接上代码：
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deads = new HashSet<>();
for(String w:deadends){
deads.add(w);
}
Set<String> visited = new HashSet<>();
Queue<String> p = new LinkedList<>();
int step = 0;
visited.add("0000");
p.offer("0000");
while(!p.isEmpty()){
for(int i=0; i<p.size(); i++){
String cur = p.poll(); //poll取队首元素并删除
if(deads.contains(cur)){
continue;
}
if(cur.equals(target)){ //equals方法对比字符串
return step;
}
for(int j=0; j<4; j++){
String up = plusOne(cur,j);
if(!visited.contains(up)){
p.offer(up);
visited.add(up);
}
String down = minusOne(cur,j);
if(!visited.contains(down)){
p.offer(down);
visited.add(down);
}
}
}
step++;
}
return -1;
}
public String plusOne(String cur, int num){
//char c = cur.charAt(num);
char[] ch = cur.toCharArray(); //把字符串转化为字符数组再进行单个替换
if(ch[num]=='9')ch[num]='0';
else ch[num] += 1;
String s = new String(ch); //更新完后再把字符数组转化为字符串
return s;
}
public String minusOne(String cur,int num){
char[] ch = cur.toCharArray();
if(ch[num]=='0')ch[num]='9';
else ch[num] -= 1;
String s = new String(ch);
return s;
}
}好了，看上去没啥问题吧应该，样例跑一下：
第8个点就直接g，遂出现了文章开头的那段吐槽，看上去没啥问题，但不知道卡在哪里一个小点，反复对比测试打印变量，把错误范围逐渐缩小，最后发现问题出现在这里：
while(!p.isEmpty()){
//int sz = p.size();
for(int i=0; i<p.size(); i++){
.....
}
....
}这里i的循环终止在p.size()，乍看之下好像没毛病，但对BFS稍微熟悉点的人可能就看出问题了，while的每次循环应该是对每一个树层的处理，这里遍历的应该是当前树层的所有节点，这个值应该是不变的，这里的p.size()就是一个在动态变化的值了。
东哥的源码中用的是int sz,然后for循环终止在sz（上面代码中已经注释出来），常规想法：你看，要么写sz = p.size()，然后直接用sz,要么直接在循环里写p.size（），不就是一样的东西，所以在调试的过程中一直到我在while的开头和结尾分别打印了p.size才发现其实是不一样的，问题就出在这里。
其实这里涉及到一个典型的思维误区，for循环的循环终止值是每一次循环开头都要判断一次，那么每一次都要计算p.size()，同时我们在BFS扩充队列，那队列p当然是动态的，那每次循环开头进行判断的时候p.size()必然是动态值，也就是说每一层树层的结点就掺杂了下一层子节点的元素，整个BFS就崩溃了。用sz存储p.size()就是用一个变量记录本层的节点数，使之不变。所以，for的理解不深才是这个Bug的真正本质。
好了，这个bug解决了，下面来看一下双向BFS的思路：其实很简单，决策树的遍历方向是从上往下，为了找到目标需要遍历到答案层，如果我们反方向—即从目标结点从下往上也进行遍历，那么两波树枝交会的地方就是一条通路，即找到答案。所以需要再引入一个反向队列，并做同样的搜索操作，同时还可以加入了一个小优化，即每次遍历开始前对两个队列进行判断，优先对长度短的队列进行遍历和扩充，降低空间复杂度。最后这里由于元素不要求有序性，这里把两个队列和一个标记set统一成HashSet，进一步提高速度。
上代码：
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deads = new HashSet<>();
for(String w:deadends){
deads.add(w);
}
Set<String> visited = new HashSet<>();
// Queue<String> p1 = new LinkedList<>();
// Queue<String> p2 = new LinkedList<>();
Set<String> p1 = new HashSet<>();
Set<String> p2 = new HashSet<>();
int step = 0;
//visited.add("0000");
p1.add("0000");
p2.add(target);
while(!p1.isEmpty()&&!p2.isEmpty()){
//Set<String> swap = new HashSet<>();
if(p1.size()>p2.size()){
Set<String> swap = new HashSet<>();
swap = p1;
p1 = p2;
p2 = swap;
}
//Queue<String> tmp = new LinkedList<>();
Set<String> tmp = new HashSet<>();
for(String cur:p1){
//String cur = p1.poll();
if(deads.contains(cur)){
continue;
}
if(p2.contains(cur)){
return step;
}
visited.add(cur);
for(int j=0; j<4; j++){
String up = plusOne(cur,j);
if(!visited.contains(up)){
//tmp.offer(up);
tmp.add(up);
//visited.add(up);
}
String down = minusOne(cur,j);
if(!visited.contains(down)){
//tmp.offer(down);
tmp.add(down);
//visited.add(down);
}
}
}
step++;
p1 = p2;
p2 = tmp;
}
return -1;
}
public String plusOne(String cur, int num){
//char c = cur.charAt(num);
char[] ch = cur.toCharArray();
if(ch[num]=='9')ch[num]='0';
else ch[num] += 1;
String s = new String(ch);
return s;
}
public String minusOne(String cur,int num){
char[] ch = cur.toCharArray();
if(ch[num]=='0')ch[num]='9';
else ch[num] -= 1;
String s = new String(ch);
return s;
}
}小tips：BFS的step更新一般位于队列循环的末尾。
把Deque更换为HashSet后冒出了一个新的疑问，如果我在Deque 中也使用for(string cur:p)的写法会不会避免出现p.size()的bug，调试了下发现不支持，Java集合类这一块还需要好好看一下，初学基础还是太薄弱，这题的思考就记录到这里，下钟下钟。