打开转盘锁：使用图的广度优先遍历实现
Java
https://leetcode-cn.com/problems/open-the-lock/
解题思路
使用图的广度优先遍历思想来实现，字符串处理得比较慢，可以使用哈希方法转换成对应的整型。再者图比较大，搜索速度受限于广度，可以使用双向广度优先遍历优化（没实现，同学们可以自己尝试）。
在求解问题的时候，之前的都是实实在在给出了可以遍历的情况，从而很明显可以看出那个问题是个图论问题，而在这个问题中，并没有很明显的给出图论问题的模型，需要我们自己去建模。在本问题中，锁的每个状态可以看做是图中的每个顶点，而从一种状态变成另一种状态就是求其“路径”的过程，如上图所示，对于0000这个状态，与其直接连接的（即可以通过一步操作变成的）状态就有8种，随之这8种状态还有很多种，而“1000”与“0100”也都可以通过一步操作到达“1100”状态，所以更加说明其是个多对多的关系，即图所描述的关系，这类问题是关于状态表达的问题。有了以上的转换，那么这个题就转换成了无权无向图的最短路径问题。
代码
import java.util.ArrayList;
import java.util.HashMap;
/**
* @author Minuy
* @time 21:04
* @date 2021/11/20
*/
public class Solution {
int[] deadends;
/**
* 优化，
* 1. 死亡数组可以转成哈希的形式加快判断
* 2. 目标不可达可以直接返回
* 3. 是否遍历跟距离可以一并存储处理
* 4. 字符串范围为0-9999，整个可以使用整型数字来代替以加快速度
*/
public int openLock(String[] deadends, String target) {
// 转换成对应的哈希值，加快判定速度
this.deadends = new int[deadends.length];
for (int i = 0; i < deadends.length; i++) {
this.deadends[i] = hash(deadends[i]);
}
int sta = hash("0000");
int tar = hash(target);
if(isDead(tar)){ // 目标不可达
return -1;
}
// 同时承担是否被遍历和存储当前距离的存储任务
HashMap<Integer, Integer> isVisited = new HashMap<>();
if (!isDead(sta)) { // 最开始的这个也要判断是不是凉凉的
ArrayList<Integer> queue = new ArrayList<>();
queue.add(sta);
isVisited.put(sta, 0);
if (tar == sta){ // 目标就是起始位置
return isVisited.get(tar);
}
while (!queue.isEmpty()) {
sta = queue.remove(0);
for (int s : getNextStats(sta)) {
if (!isVisited.containsKey(s)) {
queue.add(s);
// isVisited.add(s);
isVisited.put(s, isVisited.get(sta) + 1);
if (s == tar) {
return isVisited.get(tar);
}
}
}
}
}
return -1;
}
// 把分散的数组值合并
private int chartsToInt(int[] str) {
int num = str[3];
num+=str[2]*10;
num+=str[1]*100;
num+=str[0]*1000;
return num;
}
// 把字符串转换成对应的哈希值
private int hash(String str) {
int hash = str.charAt(3) - '0';
hash += (str.charAt(2) - '0') * 10;
hash += (str.charAt(1) - '0') * 100;
hash += (str.charAt(0) - '0') * 1000;
return hash;
}
// 获取与sta相邻的状态
private Iterable<Integer> getNextStats(int sta) {
ArrayList<Integer> ret = new ArrayList<>();
int[] chars = new int[4];
chars[0] = sta / 1000;
chars[1] = (sta / 100) % 10;
chars[2] = (sta / 10) % 10;
chars[3] = sta % 10;
for (int i = 0; i < chars.length; i++) {
int o = chars[i]; // 备份
// ---------------------加一操作
if (chars[i] == 9) {
chars[i] = 0;
} else {
chars[i] += 1;
}
int next = chartsToInt(chars);
if (!isDead(next)) {
ret.add(next);
}
chars[i] = o; // 恢复一下
// ---------------------减一操作
if (chars[i] == 0) {
chars[i] = 9;
} else {
chars[i] -= 1;
}
next = chartsToInt(chars);
if (!isDead(next)) {
ret.add(next);
}
chars[i] = o; // 恢复一下
}
return ret;
}
// 判断有没有触碰到死亡密码
private boolean isDead(int str) {
for (int dead : deadends) {
if (dead == str) {
return true;
}
}
return false;
}
}