问题
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
分析
问题需要的答案为给出最小的旋转次数, 不难联想到与最短、最少相关的广度优先算法. 四个圆形拨轮组合在一起之后可以想象为一个抽奖时的数字转轮.
4个位置上每次只有一个数能够进行 +1 或 -1 操作, 那么每个数经过变换之后就有2种结果, 4个数就有8种结果.
实现
判断从 ‘0000’ 到达目标数字经过的路径是否会经过死亡数字.每个拨轮的数能够+1(向前拨一下)和-1(向后拨一下) => 每个数相邻的数就将有8种.每个数和相邻的数相连就会构成一个网状图. 利用 BFS 算法查找从 0000 到目标节点的最短路径.
为了方便存储数字组合, 构建一个类 Node 来存储, 因为涉及数组的比较, 所以需要注意复写 equals 和 hashCode 方法.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Node {
int[] value;
public Node(int[] value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Arrays.equals(value, node.value);
}
@Override
public int hashCode() {
return Arrays.hashCode(value);
}
}
|
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
|
class Solution {
public int openLock(String[] deadends, String target) {
// 参数合理性检查
if (deadends == null || deadends.length < 1 || target == null) throw new NullPointerException();
// 如果目标就在死亡列表中，则直接返回 -1
for (String s : deadends) {
if (target.equals(s)) {
return -1;
}
}
Set<Node> visited = new HashSet<>(); /* 记录访问过的数字 */
Queue<Node> integers = new ArrayDeque<>(); /* BFS 访问队列 */
Node targetNode = parse(target); /* 目标节点 */
// 解析死亡列表
Node[] deads = new Node[deadends.length];
for (int i=0; i<deadends.length; i++) {
deads[i] = parse(deadends[i]);
}
int step = -1;
// 添加根节点到访问队列
integers.add(new Node(new int[]{0, 0, 0, 0}));
visited.add(integers.peek());
while (!integers.isEmpty()) {
// 每一层遍历完后，步数+1
step++;
int size = integers.size();
for (int i = 0; i < size; i++) {
Node num = integers.remove();
if (num.equals(targetNode)) {
return step;
}
// 是否属于死亡列表
boolean goon = true;
for (Node d : deads) {
if (d.equals(num)) {
goon = false;
break;
}
}
if (goon) {
// 获取邻居
Node[] neibors = getNeibor(num);
for (Node n : neibors) {
boolean contain = visited.contains(n);
if (!contain) {
integers.add(n);
visited.add(n);
}
}
}
}
}
return -1;
}
private Node[] getNeibor(Node target) {
Node[] nodes = new Node[8];
for (int i = 0, j = 0; i < 4; i++) {
int[] values = Arrays.copyOf(target.value, 4);
int num = values[i];
//+1
int add = num + 1;
add = add == 10 ? 0 : add;
values[i] = add;
nodes[j++] = new Node(Arrays.copyOf(values, 4));
//-1
int dec = num - 1;
dec = dec == -1 ? 9 : dec;
values[i] = dec;
nodes[j++] = new Node(Arrays.copyOf(values, 4));
}
return nodes;
}
private Node parse(String str) {
String[] ss = str.split("");
int[] num = new int[4];
for (int i = 0; i < 4; i++) {
num[i] = Integer.valueOf(ss[i]);
}
return new Node(num);
}
}
|
