LeetCode 752 打开转盘锁题解
[toc]
题目
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/open-the-lock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例
示例 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提示：
- 死亡列表 deadends 的长度范围为 [1, 500]。
- 目标数字 target 不会在 deadends 之中。
- 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
思路与分析
设N表示状态的位数，题目中用4个数字表示状态，因此N=4。A表示每个数字可以选择的范围的大小，题目中每个数字的选取范围是0-9共10个数字。因此总的状态个数为 A * A * A * A = A ^ N = 10 * 10 * 10 * 10 = 10^4=10000。 因此，整个搜索范围相当于1个包含10000个结点的图。如果仅转动一位数字且转动的幅度为1，得到的结果不包含在“死锁”状态即deadends数组中，则这两个状态（结点）之间有边。
题目要求最小转动次数，相当于最少次改变状态，也就是要求状态转移图上从“0000”到目标状态（结点）的最短路径。这显然可以使用广度优先搜索的算法来进行这个过程。
代码
有了这个思路，代码就不难书写了。以下采用Leetcode给出的模板来实现。更多对于性能的优化可以参考评论区以及其他的题解。
//模板
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> used; // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to used;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to used;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
class Solution {
public int openLock(String[] deadends, String target) {
//使用Hash存储“死锁状态”，以便快速判断某个状态是否存在是“死锁”状态
Set<String> dead = new HashSet<>();
for (String deadend : deadends) {
dead.add(deadend);
}
//模板中的队列及使用过的结点的hash集。因为转动锁的时候可能造成重复的状态，因此需要hash集来避免重复访问。
Queue<String> q = new LinkedList<>();
Set<String> seen = new HashSet<>();
q.offer("0000");
seen.add("0000");
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
//每个for循环表示1轮转动。
for (int i = 0; i < size; i++) {
//取出上一轮存入的结点，用pre表示。
String pre = q.poll();
//因为题目中说明目标数字 target 不会在 deadends 之中。“0000”要么不是target，要么不在deadends之中
//因此直接判断结点是否等于target即可。若当前结点不等于target，则判断当前结点是否在deadens之中，若在之中，
//则表面当前结点是不可达的，因此无需处理当前结点可能转动的状态。
if (pre.equals(target)) {
return step;
}else if (!dead.contains(pre)) {
//处理转动的状态，共有4位数字需要处理
for (int j = 0; j < 4; j++) {
//每个数字可能+1或-1
for (int k = -1; k <= 1; k += 2) {
//用于计算当前位的数字 0-9加一减一后的范围为-1-10，加上10之后为9-20，对10取模后为0-9；
int y = ((pre.charAt(j) - '0') + 10 + k) % 10;
//生成当前状态
String cur = pre.substring(0, j) + ("" + y) + pre.substring(j + 1);
if (!seen.contains(cur)) {
q.offer(cur);
seen.add(cur);
}
}
}
}
}
step += 1;
}
return-1;
}
}
