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
| class Solution {
public boolean canReach(int[] arr, int start) {
boolean[] visited = new boolean[arr.length];
Deque<Integer> q = new ArrayDeque<>();
q.offer(start);
visited[start] = true;
while (!q.isEmpty()) {
int currPos = q.poll();
if (arr[currPos] == 0) {
return true;
}
int nextPosOne = currPos + arr[currPos];
if (nextPosOne < arr.length && !visited[nextPosOne]) {
q.offer(nextPosOne);
visited[nextPosOne] = true;
}
int nextPosTwo = currPos - arr[currPos];
if (nextPosTwo >= 0 && !visited[nextPosTwo]) {
q.offer(nextPosTwo);
visited[nextPosTwo] = true;
}
}
return false;
}
}
|
BFS就完事儿了.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean canReach(int[] arr, int start) {
return dfs(arr, new boolean[arr.length], start);
}
private boolean dfs(int[] arr, boolean[] visited, int currPos) {
if (arr[currPos] == 0) {
return true;
}
visited[currPos] = true;
int nextPosOne = currPos + arr[currPos];
if (nextPosOne < arr.length && !visited[nextPosOne] && dfs(arr, visited, nextPosOne)) {
return true;
}
int nextPosTwo = currPos - arr[currPos];
if (nextPosTwo >= 0 && !visited[nextPosTwo] && dfs(arr, visited, nextPosTwo)) {
return true;
}
return false;
}
}
|
DFS就完事儿了.
时间复杂度: O(n)
空间复杂度: O(n)
