友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
752. Open the Lock
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
The lock initially starts at '0000', a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".Example 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".Example 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.Example 4:
Input: deadends = ["0000"], target = "8888"
Output: -1Note:
-
The length of
deadendswill be in the range[1, 500]. -
targetwill not be in the listdeadends. -
Every string in
deadendsand the stringtargetwill be a string of 4 digits from the 10,000 possibilities'0000'to'9999'.
思路分析
可以把题目的意思画图表示一下：
从这张图上可以看出，可以使用广度优先搜索算法来解题。这道题可以 111. Minimum Depth of Binary Tree 参考理解，不同的是： 111 是二叉树，本题是多叉树。
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
/**
* 在看到 BFS 的提示下，自己思考出来
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-29 20:59:24
*/
public int openLock(String[] deadends, String target) {
String origin = "0000";
Set<String> deads = new HashSet<>();
for (String deadend : deadends) {
// 如果起始点就在黑名单里，直接返回
if (deadend.equals(origin)) {
return -1;
}
deads.add(deadend);
}
// 保存访问过的节点，防止出现循环节点
Set<String> visited = new HashSet<>();
// 使用 BFS 来处理
Queue<String> queue = new LinkedList<>();
queue.offer(origin);
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (cur.equals(target)) {
return step;
}
// 处理过就不再处理
if (visited.contains(cur)) {
continue;
} else {
visited.add(cur);
}
// 对字符串按字符位进行加减操作
for (int j = 0; j < cur.length(); j++) {
String plus = plus(cur, j);
if (!deads.contains(plus)) {
queue.offer(plus);
}
String minus = minus(cur, j);
if (!deads.contains(minus)) {
queue.offer(minus);
}
}
}
step++;
}
return -1;
}
private String plus(String str, int index) {
StringBuilder sb = new StringBuilder(str);
char c = sb.charAt(index);
if (c == '9') {
c = '0';
} else {
c += 1;
}
sb.replace(index, index + 1, String.valueOf(c));
return sb.toString();
}
private String minus(String str, int index) {
StringBuilder sb = new StringBuilder(str);
char c = sb.charAt(index);
if (c == '0') {
c = '9';
} else {
c -= 1;
}
sb.replace(index, index + 1, String.valueOf(c));
return sb.toString();
}