LeetCode Notes_#752 打开转盘锁
Contents
题目
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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" 时这个锁就会被锁定。提示：
- 死亡列表 deadends 的长度范围为 [1, 500]。
- 目标数字 target 不会在 deadends 之中。
- 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
思路分析
题目描述的是一个很具体的问题，但是乍一看是没有什么思路的，需要将问题转化，将问题抽象成一个状态转移的问题。
将0000~9999看作不同的状态，这些状态之间可以互相转换。
转换的条件是，两个数字仅有一位相差1（0和9也算在内）。
按照上述描述，可以画出一个状态转移图，图中有0000~9999这些节点，满足状态转移条件的节点之间有边连接。最小旋转次数就等于从起始状态0000到target的最短路径。
求最短路径的一个方法就是广度优先遍历BFS,广度优先遍历也就是层序遍历，从0000到target的过程中，广度优先遍历的层数就是最短路径。具体写法类似于树的BFS。
需要注意的点：
- 状态转移的过程不可以出现
deadends里的元素，遇到了就直接跳过 - BFS过程中，可能出现重复访问的节点，所以还需要判断重复，如果是重复的节点就不入队
- 需要使用
null作为层与层之间的分隔符，否则不好计数
解答
class Solution {
public int openLock(String[] deadends, String target) {
//两个HashSet，用于判断重复
HashSet<String> dead = new HashSet<>();
for(String str:deadends){
dead.add(str);
}
HashSet<String> seen = new HashSet<>();
//创建BFS用到的队列，先把遍历的起点‘0000’入队
Queue<String> queue = new LinkedList<>();
queue.offer("0000");
//第一层只有只有一个节点，所以加入分隔符
queue.offer(null);
//计数器，记录路径的长度
int depth = 0;
while(!queue.isEmpty()){
String cur = queue.poll();
//null是层与层之间的分隔符
if(cur == null){
//遇到null说明接下来的元素就是新的一层了，depth增加1
depth++;
//判断下一层是否还有元素，如果有，就要添加null到队尾（因为这时下一层已经全部入队）
//这时添加到队尾，刚好就可以分隔开下一层与下下层
if(queue.peek() != null)
queue.offer(null);
}else if(cur.equals(target)){
return depth;
//如果cur在dead当中，就不能从这个节点走，在循环中不做任何操作，直接进入下一轮循环
//否则，就把cur的所有邻居节点入队，等待遍历
}else if(!dead.contains(cur)){
//外层循环：4位数
for(int i = 0;i <= 3;i++){
//内层循环：加1或者减1（加-1）
for(int d = -1;d <= 1;d += 2){
//修改的那一位数字，记为newDigit
//求余是为了符合0，9之间的转换
int newDigit = ((cur.charAt(i) - '0') + d + 10) % 10;
//将newDigit拼接到cur字符串的合适位置
String StringNeibor = cur.substring(0,i) + newDigit + cur.substring(i+1);
//对于每个邻居节点，需要判断是否是已经访问过的，如果已经访问过，就不再入队
if(!seen.contains(StringNeibor)){
seen.add(StringNeibor);
queue.offer(StringNeibor);
}
}
}
}
}
//最后没找到，就返回-1
return -1;
}
}复杂度分析
时间复杂度：O(N2 * AN + D)。我们用 A 表示数字的个数，N 表示状态的位数，D表示数组 deadends 的大小。在最坏情况下，我们需要搜索完所有状态，状态的总数为 O(AN)。对于每个状态，我们要枚举修改的位置，需要 O(N) 的时间，枚举后得到新的状态同样需要 O(N) 的时间。
空间复杂度：O(AN + D))，用来存储队列以及 deadends 的集合。