打开转盘锁是大厂算法题中比较常见的一道题，是一个典型的BFS的解法，也是有前的的解法的，这里就不多论述，本文旨在使用BFS解决本题。
说到BFS（广度优先搜索算法），就不得不说一下DFS（深度优先搜索算法），其中DFS就是回溯算法，是一种循环递归的方法，常用于解决求解“所少种答案”类型的问题，它的搜索方式按照一条路径搜索到最底层，然后返回到上一层次继续递归搜索。而BFS常用于解决“最值”问题，它的搜索方式和DFS是有差异的，是当前节点周围的所有的节点，一层一层的向下搜索，所以常用于搜索最短路径问题。
说到最值问题，我们之前也讲过了“动态规划”也是用于求解最值问题的，那我们怎么选择呢？这个要看当前问题是否有最优子结构，比如说一个问题的最优解依赖它的子问题里面的最优解，这个时候应该使用“动态规划”，而当前的打开转盘锁，并没有最优子结构，所以不适用于“动态规划”。
BFS是我们经常会遇到的问题，也是可以总结出一套对应的BFS问题框架的：
// 计算从起点到目标target的最小距离
int bfs(TreeNode start, TreeNode target) {
// DFS的核心数据结构，用来存储当前节点所有周围节点
Queue<TreeNode> q;
// 集合用来存储已经访问过的节点，避免重复访问，提供执行效率
Set<TreeNode> set;
q.add(start);
set.add(start);
// 记录步数
int step = 0;
while(!q.isEmpty()) {
// 这里需要记录当前的队列的大小，因为后面会不断从队列中删除数据
int size = q.size();
for (int i = 0; i < size; i ) {
TreeNode cur = q.poll();
// 这里判断当前节点是否是目标节点
if (cur is target) {
// 如果是的话，直接返回，DFS的本质是搜索最短路径的
return step;
}
// 如果不是的话，要将当前节点的周围的节点加入队列
for(TreeNode node :cur.child()) {
//要判断节点是否已经访问过了，访问过的就不要再加入了，相当于一个剪枝的优化手段
if (node is not in set) {
q.add(node);
set.add(node);
}
}
}
// 这里是重点，步数的增加是在这里
step ;
}
}
下面进行代码的书写，代码中加了详细注释。
public static int openLock(String[] deadends, String target) {
// 当0000就是目标值的时候，直接返回0
if ("0000".equals(target)) {
return 0;
}
// 当0000就是死亡数字的时候，直接返回-1
for (int i = 0; i < deadends.length; i ) {
if ("0000".equals(deadends[i])) {
return -1;
}
}
// 核心数据结构，用来记录一个节点的周围的所有的节点
Queue<String> queue = new LinkedList<>();
// 用来记录已经访问过的节点，避免重复访问
Set<String> set = new HashSet<>();
// 永远下面转轮上转和下转，定义到这里避免重复创建
boolean[] flag = {true, false};
queue.add("0000");
set.add("0000");
set.addAll(Arrays.asList(deadends));
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i ) {
String cur = queue.poll();
// 判断当前是否满足目标
if (target.equals(cur)) {
return step;
}
for (int j = 0; j < 4; j ) {
// 循环true和false的写法
for (int k = 0; k < flag.length; k ) {
String change = change(cur, j, flag[k]);
// 如果当前节点没有被访问过，就加入到队列中
if (!set.contains(change)) {
queue.add(change);
set.add(change);
}
}
}
}
step ;
}
return -1;
}
// ser 是需要转动的密码，num是转动第几位密码，from是向上还是向下转 true向上转，false 向下转
public static String change(String ser, int num, boolean from) {
char[] chars = ser.toCharArray();
char c = ser.charAt(num);
if (c == '9' && from) {
c = '0';
} else if (c == '0' && !from) {
c = '9';
} else if (from) {
c ;
} else {
c--;
}
chars[num] = c;
return new String(chars);
}
到这里本文就结束了，在写算法问题时要判断出当前问题可以使用什么解法，比如上面说的“最值”问题，对应的有“动态规划”和今天的BFS，但是动态规划问题存在最优子结构，本题并不存在最优子结构，所有应该考虑使用BFS解决问题。
点赞关注一下哈，以后继续分享。
