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
| class Solution {
private static class Node {
int pos;
boolean canMoveBack;
Node(int _pos, boolean _canMoveBack) {
pos = _pos;
canMoveBack = _canMoveBack;
}
}
public int minimumJumps(int[] forbidden, int a, int b, int x) {
if (x == 0) {
return 0;
}
int furthest = 2000 + 2 * b + 1;
boolean[] visited = new boolean[furthest];
for (int num : forbidden) {
visited[num] = true;
}
int step = 0;
Queue<Node> q = new LinkedList<>();
q.add(new Node(0, false));
visited[0] = true;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node currNode = q.poll();
if (currNode.pos == x) {
return step;
}
if (currNode.canMoveBack && currNode.pos - b > 0 && !visited[currNode.pos - b]) {
q.offer(new Node(currNode.pos - b, false));
visited[currNode.pos - b] = true;
}
if (currNode.pos + a < furthest && !visited[currNode.pos + a]) {
q.offer(new Node(currNode.pos + a, true));
visited[currNode.pos + a] = true;
}
}
step += 1;
}
return -1;
}
}
|
BFS就是. 关键在于什么时候停. 我看评论区, upper bound是max(num in forbidden, x) + a + b. 但我也不知道为啥.
然后就BFS.
最大的问题就是for循环中要先添加backward, 再添加forward, 要不然不会通过. 我想了很久也不知道为什么.
时间复杂度和空间复杂度我也不知道是什么.
以下是反面教材, 失败的尝试
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
| class Solution {
public int minimumJumps(int[] forbidden, int a, int b, int x) {
Map<Integer, Integer> visited = new HashMap<>();
Set<Integer> forbid = new HashSet<>();
for (int pos : forbidden) {
forbid.add(pos);
}
int currPos = 0, backPos = 0, step = 0;
while (backPos <= x) {
if (forbid.contains(currPos)) {
break;
} else {
if (!visited.containsKey(currPos)) {
visited.put(currPos, step);
}
if (!forbid.contains(backPos) && !visited.containsKey(backPos)) {
visited.put(backPos, step + 1);
}
}
currPos += a;
backPos = currPos - b;
step += 1;
}
return visited.containsKey(x) ? visited.get(x) : -1;
}
}
|
失败的尝试. 以为就是往前走一步, 退一步, 然后在退之前的位置再继续走一步退一步. 但我没考虑到退完一步再往前走还有新的可能. 因此这个答案是错误的.
