leetcode752-打开转盘锁

原题

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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. 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 ‘0000’ 到 ‘9999’ 中产生。

解法

思想

其实是一个树的BFS搜索问题:

每层示意图

用Queue来得到每层的节点。

主要需要注意的地方有:

  • 为了避免重复的节点进入队列,可以使用数组记录是否出现过,或是用HashSet记录出现过的节点。
  • 当遇到死亡数字数组中的元素时也不能将该元素添加至队列中。
  • 当搜索到题目要求的元素时,为了得到当前层数,有两种方法:
    1. 用一个数据结构表示节点,记录节点的值和层数。
    2. 每层元素入队列之后再加入一个null元素,每次遍历到null元素即可知道遍历完了了一层。

代码

我一开始是这样写的:

//节点的数据结构,需要记录层数
class Node{
    public String value;
    public int count;
    public Node(String value,int count){
        this.value = value;
        this.count = count;
    }
}

class Solution {
    public int openLock(String[] deadends, String target) {
        //如果死亡数组中存在0000直接返回-1
        if(arrayContains(deadends,"0000")) return -1;
        //标记数组用于记录哪些数字出现过
        int[] mark = new int[10000];
        //0000出现过
        mark[0] = 1;

        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(new Node("0000",0));

        while(!queue.isEmpty()){
            //获取队列头
            Node node = queue.poll();
            if(node.value.equals(target)) return node.count;
            else {
                char[] charArray = node.value.toCharArray();
                for(int i = 0;i<4;i++) {
                    //位于第i位的数字+1,如果是9变成0
                    char[] plusOneCharArray = Arrays.copyOf(charArray,charArray.length);
                    plusOneCharArray[i] = (char) (charArray[i]=='9'?'0':charArray[i]+1);
                    String plusOne = String.valueOf(plusOneCharArray);
                    if(plusOne.equals(target)) 
                        return node.count+1;
                    //没有出现过且不在死亡数字中才添加至队列中
                    if((!arrayContains(deadends, plusOne))&&mark[Integer.valueOf(plusOne)]==0) {
                        queue.offer(new Node(plusOne,node.count+1));
                        mark[Integer.valueOf(plusOne)] = 1;
                    }
                    //位于第i位的数字-1,如果是0变成9                
                    char[] minusOneCharArray = Arrays.copyOf(charArray,charArray.length);
                    minusOneCharArray[i] = (char) (charArray[i]=='0'?'9':charArray[i]-1);
                    String minusOne = String.valueOf(minusOneCharArray);
                    if(minusOne.equals(target)) 
                        return node.count+1;
                    //没有出现过且不在死亡数字中才添加至队列中
                    if((!arrayContains(deadends, minusOne))&&mark[Integer.valueOf(minusOne)]==0) {
                        queue.offer(new Node(minusOne,node.count+1));
                        mark[Integer.valueOf(minusOne)] = 1;
                    }

                }
            }
        }

        return -1;
    }

    //遍历数组,用于检测死亡数字中是否存在指定的数字
    public boolean arrayContains(String[] stringArray,String toFind) {
        for(String i:stringArray) {
            if(i.equals(toFind)) return true;
        }
        return false;
    }
}

然后发现上面这种方法需要的时间贼久,最后强行理解了一下发现问题主要出在检测死亡数组中是否存在指定数字的时候,时间开销太高了。

最后还是换成了用HashSet检测死亡数组中是否存在指定的数字:

class Node{
    public String value;
    public int count;
    public Node(String value,int count){
        this.value = value;
        this.count = count;
    }
}

class Solution {
    public int openLock(String[] deadends, String target) {
        //将死亡数字全部加进一个HashSet中
        Set<String> set = new HashSet<String>();
        for(String i:deadends) {
            if(i.equals("0000"))
                return -1;
            set.add(i);
        }

        int[] mark = new int[10000];
        mark[0] = 1;
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(new Node("0000",0));

        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.value.equals(target)) return node.count;
            else {
                char[] charArray = node.value.toCharArray();
                for(int i = 0;i<4;i++) {
                    char[] plusOneCharArray = Arrays.copyOf(charArray,charArray.length);
                    plusOneCharArray[i] = (char) (charArray[i]=='9'?'0':charArray[i]+1);
                    String plusOne = String.valueOf(plusOneCharArray);
                    if(plusOne.equals(target)) 
                        return node.count+1;
                    if((!set.contains(plusOne))&&mark[Integer.valueOf(plusOne)]==0) {
                        queue.offer(new Node(plusOne,node.count+1));
                        mark[Integer.valueOf(plusOne)] = 1;
                    }

                    char[] minusOneCharArray = Arrays.copyOf(charArray,charArray.length);
                    minusOneCharArray[i] = (char) (charArray[i]=='0'?'9':charArray[i]-1);
                    String minusOne = String.valueOf(minusOneCharArray);
                    if(minusOne.equals(target)) 
                        return node.count+1;
                    if((!set.contains(minusOne))&&mark[Integer.valueOf(minusOne)]==0) {
                        queue.offer(new Node(minusOne,node.count+1));
                        mark[Integer.valueOf(minusOne)] = 1;
                    }

                }
            }
        }

        return -1;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode752-%e6%89%93%e5%bc%80%e8%bd%ac%e7%9b%98%e9%94%81/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月6日
下一篇 2019年12月10日

相关推荐

  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例: 输入: [1,2,1,3,2,5] 输出: [3,5…

    算法 2020年4月28日
    0140
  • leetcode98-验证二叉搜索树

    原题 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和…

    算法 2020年1月15日
    0120
  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣(LeetCode) 解法 思想 这道题题目有点难理解,其实就是上下左右搜索,质量有点低了。 代码 class Solution { cha…

    算法 2020年3月26日
    070
  • leetcode707-设计链表

    原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用…

    算法 2019年12月14日
    0290
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110
  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    0100
  • leetcode118-杨辉三角

    原题 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]…

    2019年11月15日
    0100
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 5天前
    030
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01220

发表回复

登录后才能评论