原题

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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;
    }
}