题目描述
一个密码锁由 4 个环形拨轮组成，每个拨轮都有 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
提示：
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target 不在 deadends 之中target 和 deadends[i] 仅由若干位数字组成
注意：本题与主站 752 题相同： https://leetcode.cn/problems/open-the-lock/
解法
方法一
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 | class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
s = set(deadends)
if target in s or '0000' in s:
return -1
if target == '0000':
return 0
def prev(c):
return '9' if c == '0' else str(int(c) - 1)
def next(c):
return '0' if c == '9' else str(int(c) + 1)
def get(t):
res = []
t = list(t)
for i in range(4):
c = t[i]
t[i] = prev(c)
res.append(''.join(t))
t[i] = next(c)
res.append(''.join(t))
t[i] = c
return res
visited = set()
q = deque([('0000', 0)])
while q:
status, step = q.popleft()
for t in get(status):
if t in visited or t in s:
continue
if t == target:
return step + 1
q.append((t, step + 1))
visited.add(t)
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 | class Solution {
public int openLock(String[] deadends, String target) {
Set<String> s = new HashSet<>(Arrays.asList(deadends));
if (s.contains(target) || s.contains("0000")) {
return -1;
}
if (Objects.equals(target, "0000")) {
return 0;
}
Set<String> visited = new HashSet<>();
Deque<String> q = new ArrayDeque<>();
q.offerLast("0000");
int step = 0;
while (!q.isEmpty()) {
++step;
for (int i = 0, n = q.size(); i < n; ++i) {
String status = q.pollFirst();
for (String t : get(status)) {
if (visited.contains(t) || s.contains(t)) {
continue;
}
if (Objects.equals(t, target)) {
return step;
}
q.offerLast(t);
visited.add(t);
}
}
}
return -1;
}
private char prev(char c) {
return c == '0' ? '9' : (char) (c - 1);
}
private char next(char c) {
return c == '9' ? '0' : (char) (c + 1);
}
private List<String> get(String t) {
List res = new ArrayList<>();
char[] chars = t.toCharArray();
for (int i = 0; i < 4; ++i) {
char c = chars[i];
chars[i] = prev(c);
res.add(String.valueOf(chars));
chars[i] = next(c);
res.add(String.valueOf(chars));
chars[i] = c;
}
return res;
}
}
|
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 | class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> s(deadends.begin(), deadends.end());
if (s.count(target) || s.count("0000")) return -1;
if (target == "0000") return 0;
unordered_set<string> visited;
queue<string> q;
q.push("0000");
int step = 0;
while (!q.empty()) {
++step;
for (int i = 0, n = q.size(); i < n; ++i) {
string status = q.front();
q.pop();
for (auto t : get(status)) {
if (visited.count(t) || s.count(t)) continue;
if (t == target) return step;
q.push(t);
visited.insert(t);
}
}
}
return -1;
}
char prev(char c) {
return c == '0' ? '9' : (char) (c - 1);
}
char next(char c) {
return c == '9' ? '0' : (char) (c + 1);
}
vector<string> get(string& t) {
vector<string> res;
for (int i = 0; i < 4; ++i) {
char c = t[i];
t[i] = prev(c);
res.push_back(t);
t[i] = next(c);
res.push_back(t);
t[i] = c;
}
return res;
}
};
|
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 | func openLock(deadends []string, target string) int {
dead := map[string]bool{}
for _, s := range deadends {
dead[s] = true
}
if dead["0000"] {
return -1
}
if target == "0000" {
return 0
}
q := []string{"0000"}
visited := map[string]bool{"0000": true}
step := 0
for len(q) > 0 {
step++
size := len(q)
for i := 0; i < size; i++ {
cur := q[0]
q = q[1:]
for j := 0; j < 4; j++ {
for k := -1; k <= 1; k += 2 {
next := cur[:j] + string((cur[j]-'0'+byte(k)+10)%10+'0') + cur[j+1:]
if next == target {
return step
}
if !dead[next] && !visited[next] {
q = append(q, next)
visited[next] = true
}
}
}
}
}
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 | class Solution {
func openLock(_ deadends: [String], _ target: String) -> Int {
let deadSet = Set(deadends)
if deadSet.contains(target) || deadSet.contains("0000") {
return -1
}
if target == "0000" {
return 0
}
var visited = Set<String>()
var queue = ["0000"]
visited.insert("0000")
var step = 0
while !queue.isEmpty {
step += 1
for _ in 0..<queue.count {
let status = queue.removeFirst()
for neighbor in getNeighbors(status) {
if visited.contains(neighbor) || deadSet.contains(neighbor) {
continue
}
if neighbor == target {
return step
}
queue.append(neighbor)
visited.insert(neighbor)
}
}
}
return -1
}
private func getNeighbors(_ lock: String) -> [String] {
var neighbors = [String]()
var chars = Array(lock)
for i in 0..<4 {
let original = chars[i]
chars[i] = prevChar(original)
neighbors.append(String(chars))
chars[i] = nextChar(original)
neighbors.append(String(chars))
chars[i] = original
}
return neighbors
}
private func prevChar(_ c: Character) -> Character {
return c == "0" ? "9" : Character(UnicodeScalar(c.asciiValue! - 1))
}
private func nextChar(_ c: Character) -> Character {
return c == "9" ? "0" : Character(UnicodeScalar(c.asciiValue! + 1))
}
}
|