LeetCode752. 打开转盘锁
LeetCode752. 打开转盘锁
本文最后更新于 517 天前，其中的信息可能已经有所发展或是发生改变。
一、认识
最近跟朋友聊到刷题，朋友建议我先将思路写下来，理清楚了再开始写代码。这样做确实有好处，因为写思路时，会更早的发现问题，解决了，想清楚了，再去写代码。这样就能避免走很多弯路。
做这道题的时候，就没有盲目的开始写了。先把思路写出来，写的时候就发现了问题，并解决它，才开始写代码。因此，这次写的代码都没有浪费，以前刷题时经常写一些最终没用到的代码。
在生活中也是，遇到问题时，不妨先思考下，一步一步想清楚，没问题了再动手。也许会多花些时间，但会让你的行动更周全。
二、思路
BFS算法，轮子可以上下旋转，先广搜，遇到目标返回步数，遇到死亡数字时不加入队列。如果为初始值0000也不加入队列，回头路用set有问题，轮子上下旋转得到的节点步数不一样，这块得注意，再想想。
终止条件就是转到9，中间重复的通过set排除，但是反方向的不应该排除啊！
正反方向分开计算，就可以避免上诉情况。
如果把两个方向合在一起，就是19*4的矩形，将两个方向的节点坐标区分下，反方向x坐标用负数表示，应该能解决上诉问题。
三、题目
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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
解释：
无法旋转到目标数字且不被锁定。示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1提示：
- 死亡列表
deadends的长度范围为[1, 500]。 - 目标数字
target不会在deadends之中。 - 每个
deadends和target中的字符串的数字会在 10,000 个可能的情况'0000'到'9999'中产生。
Related Topics
- 广度优先搜索
\n
- 👍 211
- 👎 0
四、代码
class Solution {
private HashSet<String> deadendsSet;
public int openLock(String[] deadends, String target) {
initDeadendsSet(deadends);
Queue<String> queue=new LinkedList<>();
Set<String> visited=new HashSet<>();
queue.add("0000");
visited.add("0000");
int step = 0;
while (queue.size() > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String poll = queue.poll();
if (compareDeadend(poll)){
continue;
}
if (compareTarget(poll,target)){
return step;
}
int[] arr=(int[])convert(poll);
for (int j = 0; j < 4; j++) {
int[] tmp = new int[4];
tmp[0]=arr[0];
tmp[1] = arr[1];
tmp[2] = arr[2];
tmp[3] = arr[3];
if (arr[j] > -9) {
tmp[j] = arr[j]-1;
addQueue(visited,tmp,queue);
}
if (arr[j] < 9) {
tmp[j] = arr[j]+1;
addQueue(visited,tmp,queue);
}
}
}
step++;
}
return -1;
}
private void addQueue(Set<String> visited, int[] tmp, Queue<String> queue){
String convert = (String) convert(tmp);
if (!visited.contains(convert)){
queue.add(convert);
visited.add(convert);
}
}
private Object convert(Object obj) {
if (obj instanceof String) {
String str=(String) obj;
boolean flag=true;
int res[]=new int[4];
int index=0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '-') {
flag=false;
continue;
}
if (flag) {
res[index++] = c-'0';
}else {
res[index++] = 0-(c-'0');
flag=true;
}
}
return res;
}else{
int[] obj1 = (int[]) obj;
StringBuilder result = new StringBuilder();
for (int i = 0; i < 4; i++) {
result.append(obj1[i]);
}
return result.toString();
}
}
private Boolean compareTarget(String curr,String target){
return target.equals(convertAdd10(curr));
}
private String convertAdd10(String curr){
int[] ints = (int[]) convert(curr);
for (int i = 0; i < 4; i++) {
if(ints[i]<0){
ints[i]+=10;
}
}
return(String)convert(ints);
}
private Boolean compareDeadend(String target){
return deadendsSet.contains(convertAdd10(target));
}
private String convertToString(String str) {
StringBuilder sb = new StringBuilder();
for (char c :
str.toCharArray()) {
if (c!='-') {
sb.append(c);
}
}
return sb.toString();
}
private void initDeadendsSet(String[] deadends) {
deadendsSet = new HashSet<String>();
for (String deadend :
deadends) {
deadendsSet.add(deadend);
}
}
}Post Views: 252
腾讯云开发者
