leetcode回顾——Open the Lock

LeetCode

题目

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

提示：

死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

题解

这道题其实就是一道搜索题，扭动不同位置的数字轮盘，都会有不同的结果。

既然是搜索题，就要考虑用DFS还是BFS了，题目中有一句话说到：需要给出最小的旋转次数；既然是最小的旋转次数，那么就首选BFS。而最小的旋转次数，其实就等于搜索的层数，在哪一层搜索结果中存在target值，那么最小的旋转次数就等于该层对应的层的深度

同时还要记录每次的搜索结果，如果该结果存在，那么其后的搜索结果也是存在的，因此，还需要一个hashset进行结果的唯一存储。

每次旋转都只能旋转一个拨轮的一位数字，意味着只能从0到1、1到2这样，而不能从1到3，1到8这样（1到9是可以的），因此每一个旋转位置都有两种旋转选择，要么顺时针要么逆时针，总共有四个旋转盘，因此就有16种情况，可以用双层循环进行表达，外层循环次数为旋转盘的个数，内层循环为每个转盘的转动方向（顺时针、逆时针）

AC代码

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
class Solution:
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        vis = set()
        for i in range(len(deadends)):
            vis.add(deadends[i])
        if "0000" in deadends:
            return -1
        way = (1, -1)
        q = ["0000"]
        sums = 0
        while len(q) != 0:
            length = len(q)
            for i in range(length):
                t = q.pop(0)
                if t == target:
                    return sums
                for j in range(0, 4):
                    for k in range(0, 2):
                        t_l = list(t)
                        t_l[j] = str(int((ord(t_l[j]) - ord('0') + way[k] + 10) % 10))
                        _t = ''.join(t_l)
                        if not vis.__contains__(_t):
                            vis.add(_t)
                            q.append(_t)
            sums += 1
        return -1

参考文章

752. 打开转盘锁