> LeetCode752. 打开转盘锁 - Yuyy
Yuyy
Yuyy
LeetCode752. 打开转盘锁

一、认识

最近跟朋友聊到刷题,朋友建议我先将思路写下来,理清楚了再开始写代码。这样做确实有好处,因为写思路时,会更早的发现问题,解决了,想清楚了,再去写代码。这样就能避免走很多弯路。

做这道题的时候,就没有盲目的开始写了。先把思路写出来,写的时候就发现了问题,并解决它,才开始写代码。因此,这次写的代码都没有浪费,以前刷题时经常写一些最终没用到的代码。

在生活中也是,遇到问题时,不妨先思考下,一步一步想清楚,没问题了再动手。也许会多花些时间,但会让你的行动更周全。

二、思路

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

 

提示:

  1. 死亡列表 deadends 的长度范围为 [1, 500]
  2. 目标数字 target 不会在 deadends 之中。
  3. 每个 deadendstarget 中的字符串的数字会在 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);
            }
        }
    }
    

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode752. 打开转盘锁
    一、认识 最近跟朋友聊到刷题,朋友建议我先将思路写下来,理清楚了再开始写代码。这样做确实有好处,因为写思路时,会更早的发现问题,解决了,想清楚了,再去写代码。这样就能避免走很…
    扫描二维码继续阅读
    2021-01-27
    友情链接
    标签
    归档
    近期文章