题目描述
你有一个带有四个圆形拨轮的转盘锁。
每个拨轮都有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
解释：无法旋转到目标数字且不被锁定。
提示：
1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成题目解析
由题意可知：拨轮可以自由旋转。即 0 -> 9; 9 -> 0;
- 那么
0 -> 1也是一种可能，所以有：对于数字0，可以变为9或者1
- 锁的初始数字是
0000 - 那么拨动一次之后有可能有 8 种结果
- 即：
1000;90000100;09000010;00900001;0009
- 8 种可能的结果再次拨动，就是
64种结果 - 直到 找到可以解锁的数字
target - 考虑到 转动到死亡数字，锁会被锁死，那么当遇到死亡数字的时候直接跳过当前这一种可能的结果
- 其中怎么模拟 转盘锁 转动是需要好好考虑的
show code
class Solution {
public int openLock(String[] deadends, String target) {
// 初始化数字为 0000
if("0000".equals(target)) {
return 0;
}
int targetNum = 0;
for (int i = 0; i < target.length(); i++) {
// 把解锁字符串，转成数字.
targetNum = targetNum * 10 + (target.charAt(i) - '0');
}
// 把死锁所代表的数字 转存起来
Set<Integer> deadNum = new HashSet<>();
for (String deadend : deadends) {
int num = 0;
for(int i = 0;i < deadend.length();i++) {
num = num * 10 + (deadend.charAt(i) - '0');
}
deadNum.add(num);
}
if(deadNum.contains(0)) {
return -1;
}
// 我需要一个集合来保存出现过的数字，这里不用 string 因为会导致频繁创建对象
Set<Integer> repeat = new HashSet<>();
repeat.add(0);
// 每一次转动产生的结果用一个 队列保存起来
Deque<Integer> queue = new LinkedList<>();
queue.offer(0);
// 锁转动次数
int ans = 0;
while(!queue.isEmpty()) {
int sz = queue.size();
while (sz > 0) {
// 取出一个数字
Integer poll = queue.poll();
// 找到了解锁数字，直接返回
if(poll.equals(targetNum)) {
return ans;
}
// 开始转动 转盘锁
// 定义四个数字，分别代表 转盘锁的四个位置
int a = 0,b = 0,c = 0,d = 0;
d = poll % 10;
poll /= 10;
c = poll % 10;
poll /= 10;
b = poll % 10;
poll /= 10;
a = poll % 10;
// 可以出现 8 种组合
// a 转动
int aUp = ((a + 1) == 10?0:(a + 1)) * 1000;
int computeRet = aUp + b * 100 + c * 10 + d;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
int aLow = ((a - 1) == -1?9:(a - 1)) * 1000;
computeRet = aLow + b * 100 + c * 10 + d;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
// b 转动
int bUp = ((b + 1) == 10?0:(b + 1)) * 100;
computeRet = a * 1000 + bUp + c * 10 + d;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
int bLow = ((b - 1) == -1?9:(b - 1)) * 100;
computeRet = a * 1000 + bLow + c * 10 + d;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
// c 转动
int cUp = ((c + 1) == 10?0:(c + 1)) * 10;
computeRet = a * 1000 + b * 100 + cUp + d;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
int cLow = ((c - 1) == -1?9:(c - 1)) * 10;
computeRet = a * 1000 + b * 100 + cLow + d;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
// d 转动
int dUp = (d + 1) == 10?0:(d + 1);
computeRet = a * 1000 + b * 100 + c * 10 + dUp;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
int dLow = (d - 1) == -1?9:(d - 1);
computeRet = a * 1000 + b * 100 + c * 10 + dLow;
if(!deadNum.contains(computeRet) && !repeat.contains(computeRet)) {
repeat.add(computeRet);
queue.offer(computeRet);
}
sz--;
}
ans++;
}
return -1;
}
}