打开转盘锁

问题

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。

分析

问题需要的答案为给出最小的旋转次数, 不难联想到与*最短*、*最少*相关的广度优先算法. 四个圆形拨轮组合在一起之后可以想象为一个抽奖时的数字转轮.

数字转轮

4个位置上每次只有一个数能够进行 +1 或 -1 操作, 那么每个数经过变换之后就有2种结果, 4个数就有8种结果.

图

实现

判断从 ‘0000’ 到达目标数字经过的路径是否会经过死亡数字.每个拨轮的数能够+1(向前拨一下)和-1(向后拨一下) => 每个数相邻的数就将有8种.每个数和相邻的数相连就会构成一个网状图. 利用 BFS 算法查找从 0000 到目标节点的最短路径.

为了方便存储数字组合, 构建一个类 Node 来存储, 因为涉及数组的比较, 所以需要注意复写 equals 和 hashCode 方法.

class Node {
    int[] value;

    public Node(int[] value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return Arrays.equals(value, node.value);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(value);
    }
}
class Solution {

    public int openLock(String[] deadends, String target) {
        // 参数合理性检查
        if (deadends == null || deadends.length < 1 || target == null) throw new NullPointerException();
        // 如果目标就在死亡列表中,则直接返回 -1
        for (String s : deadends) {
            if (target.equals(s)) {
                return -1;
            }
        }

        Set<Node> visited = new HashSet<>(); /* 记录访问过的数字 */
        Queue<Node> integers = new ArrayDeque<>(); /* BFS 访问队列 */
        Node targetNode = parse(target); /* 目标节点 */

        // 解析死亡列表
        Node[] deads = new Node[deadends.length];
        for (int i=0; i<deadends.length; i++) {
            deads[i] = parse(deadends[i]);
        }

        int step = -1;
         // 添加根节点到访问队列
        integers.add(new Node(new int[]{0, 0, 0, 0}));
        visited.add(integers.peek());

        while (!integers.isEmpty()) {
            // 每一层遍历完后,步数+1
            step++;
            int size = integers.size();
            for (int i = 0; i < size; i++) {
                Node num = integers.remove();
                if (num.equals(targetNode)) {
                    return step;
                }

                // 是否属于死亡列表
                boolean goon = true;
                for (Node d : deads) {
                    if (d.equals(num)) {
                        goon = false;
                        break;
                    }
                }

                if (goon) {
                    // 获取邻居
                    Node[] neibors = getNeibor(num);
                    for (Node n : neibors) {
                        boolean contain = visited.contains(n);
                        if (!contain) {
                            integers.add(n);
                            visited.add(n);
                        }
                    }
                }
            }
        }
        return -1;
    }

    private Node[] getNeibor(Node target) {
        Node[] nodes = new Node[8];
        for (int i = 0, j = 0; i < 4; i++) {
            int[] values = Arrays.copyOf(target.value, 4);
            int num = values[i];

            //+1
            int add = num + 1;
            add = add == 10 ? 0 : add;
            values[i] = add;
            nodes[j++] = new Node(Arrays.copyOf(values, 4));

            //-1
            int dec = num - 1;
            dec = dec == -1 ? 9 : dec;
            values[i] = dec;
            nodes[j++] = new Node(Arrays.copyOf(values, 4));
        }
        return nodes;
    }

    private Node parse(String str) {
        String[] ss = str.split("");
        int[] num = new int[4];
        for (int i = 0; i < 4; i++) {
            num[i] = Integer.valueOf(ss[i]);
        }
        return new Node(num);
    }
}