题目描述：
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
数据范围：
$1\le arr.len \le 5 \times 10^4$
题解：
因为这个题目是只能跳到前后的两个位置，而不是之前的一段区间了，因此不能像之前那样做了。这个比较明显直接使用搜索。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
bool canReach(vector<int> &arr, int start)
{
queue<int> q;
int n = arr.size();
vector<bool> vis(n);
vis[start] = true;
q.push(start);
while (q.size())
{
auto index = q.front();
q.pop();
if (arr[index] == 0)
return true;
if (index - arr[index] >= 0 && vis[index - arr[index]] == false)
{
q.push(index - arr[index]);
vis[index - arr[index]] = true;
}
if (index + arr[index] < n && vis[index + arr[index]] == false)
{
q.push(index + arr[index]);
vis[index + arr[index]] = true;
}
}
return false;
}
};
|