752_打开转盘锁.md

打开转盘锁

752. 打开转盘锁 - 力扣（LeetCode） (leetcode-cn.com)

分析

1. BFS 广度优先遍历

把字符串当做一个节点，每次能变动一个字符达到的新字符串当做相邻的节点。如"0000"的子节点有"1000", "0100", "0010", "0001", "9000", "0900", "0090", "0009"。于是要做的就是从"0000"开始遍历寻找target。

• 队列中的节点一定是上一批节点的临近节点，所以进入循环，step++。
• 寻找队列中的每个节点的临近节点，如果不在deadends中，就加入队列和deadends (防止重复遍历)。
• 如果找到了target，返回step。
• 如果所有节点都遍历完成，说明无法找到target，返回-1。

对于两种特殊情况可以直接判断：

1. 如果target是"0000"，直接返回0。
2. 如果deadends中存在"0000"，直接返回-1。

为了方便查找字符串是否在deadends中，可以用哈希表储存deadends，花费 O(4m)的时间复杂度。m是deadends的长度。

时间复杂度为。最差情况下，枚举4位10进制的数有种可能；计算4位字符串数字需要遍历4个位置，再加上生成新字符串也需要拼接4个字符，所以是的时间复杂度。生成deadends的哈希表需要O(4m)的时间复杂度。

class Solution {
    public int openLock(String[] deadends, String target) {
        // 前置判断和处理
        if (target.equals("0000"))
            return 0;
        Set<String> deads = new HashSet<>();
        for (String d : deadends) {
            if (d.equals("0000"))
                return -1;
            deads.add(d);
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        int step = 0;
        // BFS
        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            for (int index = 0; index < size; index++) {
                String str = queue.poll();
                for (String s : getNext(str)) {
                    if (!deads.contains(s)) {
                        if (s.equals(target))
                            return step;
                        deads.add(s);
                        queue.offer(s);
                    }
                }
            }
        }
        return -1;
    }

    private List<String> getNext(String str) {
        List<String> list = new ArrayList<>();
        char[] chars = str.toCharArray();
        for (int i = 0; i < 4; i++) {
            char c = chars[i];
            chars[i] = nextPrev(c);
            list.add(new String(chars));
            chars[i] = nextBack(c);
            list.add(new String(chars));
            chars[i] = c;
        }
        return list;
    }

    private char nextPrev(char c) {
        return c == '0' ? '9' : (char) (c - 1);
    }

    private char nextBack(char c) {
        return c == '9' ? '0' : (char) (c + 1);
    }
}

2. 启发式搜索 - A*

对于启发式搜索的简单介绍可以看启发式搜索 - A*搜索算法。

启发式函数选择为：当前字符串的每一位变化到target字符串的操作次数。如0000变化为0101需要的操作次数为2次，则。

则令status表示当前字符串，next_status表示旋转一次的字符串。如果旋转令next_status更接近target了，那么；否则离target更远了，那么，而两者之间的距离。所以这个启发函数是一致的，那么每个节点只需要最多遍历一次就能得到最优解。

class Solution {
    public int openLock(String[] deadends, String target) {
        if (target.equals("0000")) return 0;
        Set<String> deads = new HashSet<>();
        for (String d : deadends) {
            if (d.equals("0000")) return -1;
            deads.add(d);
        }
        deads.add("0000");
        PriorityQueue<Astar> queue = new PriorityQueue<>((a, b) -> a.f - b.f);
        queue.offer(new Astar("0000", target, 0));
        while (!queue.isEmpty()) {
            Astar node = queue.poll();
            for (String status : get(node.status)) {
                if (!deads.contains(status)) {
                    if (status.equals(target)) return node.g + 1;
                    queue.offer(new Astar(status, target, node.g + 1));
                    deads.add(status);
                }
            }
        }
        return -1;
    }

    public char numPrev(char x) {
        return x == '0' ? '9' : (char) (x - 1);
    }

    public char numSucc(char x) {
        return x == '9' ? '0' : (char) (x + 1);
    }

    public List<String> get(String status) {
        List<String> ret = new ArrayList<String>();
        char[] array = status.toCharArray();
        for (int i = 0; i < 4; ++i) {
            char num = array[i];
            array[i] = numPrev(num);
            ret.add(new String(array));
            array[i] = numSucc(num);
            ret.add(new String(array));
            array[i] = num;
        }
        return ret;
    }

    private class Astar {
        String status;
        int f, g, h;

        Astar(String status, String target, int g) {
            this.status = status;
            this.g = g;
            this.h = getH(status, target);
            this.f = this.g + this.h;
        }

        private int getH(String status, String target) {
            int cost = 0;
            for (int index = 0; index < 4; index++) {
                int dist = Math.abs(status.charAt(index) - target.charAt(index));
                cost += Math.min(dist, 10 - dist);
            }
            return cost;
        }
    }
}