力扣、752-打开转盘锁

此题虽为中等题，但是我认为还是很有难度的，学习了东哥的思路，也就略做分享。

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

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

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定

输入: deadends = [“8888”], target = “0009”
输出：1
解释：把最后一位反向旋转一次即可 “0000” -> “0009”。

输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
输出：-1
解释：无法旋转到目标数字且不被锁定。

这个题可以典型的使用 BFS 算法，广度优先遍历算法。

要使用广度优先遍历算法的思路。总结一下：

1. 首先遍历穷举出所有的密码组合，当然穷举也是要符号一定的规律去穷举。
   比如：，从“0000”开始，转一次，会出现“1000”、“9000”、“0100”、“0900”、“0010”、“0090”、“0001”、“0009”这样共8种情况。然后到下一次，再以这 8 种密码为基础，对每种密码再转一次，就穷举出所有的情况。

2. 要考虑到在穷举的时候，是会可能走回头路的。
   比如：从“0000”走到“1000”，但是在下一次对“1000”穷举的时候，会出现“0000”，这样就会出现死循环的现象。

3. 按照题目的要求，判断到达 target 就可以结束，并返回最后记录的拨动次数。

4. 也要对 deadends 这种死亡密码进行处理，也就是说遇到这种情况就要跳过此次判断。

不多逼逼，看代码，代码中有较为详细的说明：

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Demo752 {
    public static void main(String[] args) {
        String[] str = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
        String target = "8888";
        System.out.println(openLock(str, target));
    }

    public static int openLock(String[] deadends, String target) {
        // 保存需要跳过的死亡密码
        Set<String> strings = new HashSet<>();
        for (String deadend : deadends) {
            strings.add(deadend);
        }

        // 记录已经穷举过的所有密码，防止回头路
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        //开始执行广度优先搜索
        int step = 0;
        queue.offer("0000");
        visited.add("0000");

        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                String str = queue.poll();

                //判断当前密码是否合格，不合格直接跳过
                if (strings.contains(str)) {
                    continue;
                }
                // 密码到达终点，返回路径长度
                if (str.equals(target)) {
                    return step;
                }

                // 将合格但未终点的节点末遍历相邻节点加入队列中
                // 使用4是因为字符串长度为4
                for (int j = 0; j < 4; j++) {
                    //向上拿到数据
                    String up = plusOne(str, j);
                    if (!visited.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }
                    //向下拿到数据
                    String down = minusOne(str, j);
                    if (!visited.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        // 如果穷举完，没有结果，就返回-1
        return -1;
    }

    //将当前给的数中的第j位向上拨动一位
    public static String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9') {
            ch[j] = '0';
        } else {
            ch[j] += 1;
        }
        return new String(ch);
    }

    //将当前给的数中的第j位向下拨动一位
    public static String minusOne(String str, int j) {
        char[] ch = str.toCharArray();
        if (ch[j] == '0') {
            ch[j] = '9';
        } else {
            ch[j] -= 1;
        }
        return new String(ch);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

上面这各代码就完全体现出来，广度优先遍历，从一个点开始向外一步一步的扩展开来。

再对于这个题，我们在这也是可以使用双向 BFS。
传统的 BFS 算法是从起点开始向四周继续扩散，直到遇到终点就会停止。
而双向 BFS 算法是从起点和终点同时开始扩散，当两边有交集的时候停止。

这两种思路其实从 Big O 表示法来分析的话，它两最坏的复杂度都为 O(N)，但在实际上双向的 BFS 还是会块一些的，双向 BFS 其实只需遍历半颗数就会出现结果。

不过双向 BFS 也是有一个必须的限制条件的。它必须知道终点是在哪里的。

代码演示，也有略微注释：

    public static int openLock(String[] deadends, String target) {
        // 保存需要跳过的死亡密码
        Set<String> strings = new HashSet<>();
        for (String deadend : deadends) {
            strings.add(deadend);
        }

        // 记录已经穷举过的所有密码，防止回头路
        Set<String> visited = new HashSet<>();
        Set<String> queue1 = new HashSet<>();
        Set<String> queue2 = new HashSet<>();

        //开始执行广度优先搜索
        int step = 0;
        queue1.add("0000");
        queue2.add(target);

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            // 在遍历的过程当中是不能修改 hash 表的
            // 用 temp 存储 queue1 的扩散后的结果，作为中间数
            Set<String> temp = new HashSet<>();

            // 将 queue1 中的所有节点向周围扩散
            for (String str : queue1) {

                //判断当前密码是否合格，不合格直接跳过
                if (strings.contains(str)) {
                    continue;
                }
                // 密码到达终点，返回路径长度
                if (queue2.contains(str)) {
                    return step;
                }
                visited.add(str);

                // 将合格但未终点的节点末遍历相邻节点加入队列中
                // 使用4是因为字符串长度为4
                for (int j = 0; j < 4; j++) {
                    //向上拿到数据
                    String up = plusOne(str, j);
                    if (!visited.contains(up)) {
                        temp.add(up);
                    }
                    //向下拿到数据
                    String down = minusOne(str, j);
                    if (!visited.contains(down)) {
                        temp.add(down);
                    }
                }
            }
            step++;
            
            //翻转
            queue1 = queue2;
            queue2 = temp;
        }
        // 如果穷举完，没有结果，就返回-1
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59