死亡密码

发表于 更新于 分类于 ，

简介

(Leetcode 752)

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

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

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

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

示例 1:

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

示例2：

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

示例3：

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

题解

BFS

最短路径问题，采用广度优先搜索(BFS)可以解决。为节省空间，采用双向BFS.

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
88
89
90
91
92
93
94
95
96
def openLock(deadends, target):
    if "0000" in deadends:
        return -1
    if target == "0000":
        return 0
    Qhead = ["0000"] # 第一队列，从头遍历
    Qend = [target] # 第二队列，从尾遍历
    sethead = dict() # 记录头队列所遍历过的数据及步数
    setend = dict() # 记录尾队列所遍历过的数据及步数
    sethead["0000"] = 0
    setend[target] = 0

    def upchange(ch): # 向上调整(转动)一次密码盘
        num = int(ch)
        if num == 9:
            return "0"
        return str(num + 1)

    def downchange(ch): # 向下调整(转动)一次密码盘
        num = int(ch)
        if num == 0:
            return "9"
        return str(num - 1)

    def broad(key): # 得到当前密码周围的8个其他密码
        newKey = []
        for i in range(4):
            tempStr1 = ""
            tempStr2 = ""
            t1 = upchange(key[i])
            t2 = downchange(key[i])
            for j in range(4):
                if j == i:
                    tempStr1 += t1
                    tempStr2 += t2
                else:
                    tempStr1 += key[j]
                    tempStr2 += key[j]
            newKey.append(tempStr1)
            newKey.append(tempStr2)

        return newKey

    def BFS(sethead, setend):
        while Qhead != [] and Qend != []: # 一旦某一个队列为空，说明被死亡密码封锁，无法转动到目标密码，跳出循环返回-1
            QheadLength = len(Qhead)
            QendLength = len(Qend)
            if QheadLength < QendLength: # 队列小的优先扩散，平衡空间复杂度
                for i in range(QheadLength):
                    step = sethead[Qhead[0]] # 转到当前密码所需步数
                    temp = []
                    for c in Qhead[0]:
                        temp.append(c)
                    temp = broad(temp)
                    for t in temp:
                        if t in sethead: # 记录以遍历密码，防止重复遍历
                            continue
                        if t in deadends: # 遇到死亡密码，进行下一个
                            continue
                        if t in Qhead: # 前有哈希表判断，此条件可以省略
                            continue
                        sethead[t] = step + 1 # 新的密码加入哈希表，步数加1
                        Qhead.append(t) # 新密码加入队列
                        if t in setend:
                            return sethead[t] + setend[t]
                    Qhead.pop(0) # 移除所有方向已遍历完成的密码
            else: # 结构同上
                for i in range(QendLength):
                    step = setend[Qend[0]]
                    temp = []
                    for c in Qend[0]:
                        temp.append(c)
                    temp = broad(temp)
                    for t in temp:
                        if t in setend:
                            continue
                        if t in deadends:
                            continue
                        if t in Qend:
                            continue
                        setend[t] = step + 1
                        Qend.append(t)
                        if t in sethead:
                            return sethead[t] + setend[t]
                    Qend.pop(0)
        return -1

    step = BFS(sethead, setend)
    return step


if __name__ == '__main__':
    step = openLock(["0201", "0101", "0102", "1212", "2002"], "0202")
    print(step)

[out]:6

启发式搜索

可以使用启发式搜索更快找到最小旋转次数，此处可以使用可以使用\(A^*\)算法。