Day 9:1306 跳跃游戏III
1306 跳跃游戏III
- 1. 题目描述
- 2. 解题思路
- 3. 代码实现(DFS)
- 4. 代码实现(BFS)
1. 题目描述
1306 跳跃游戏III
2. 解题思路
- 使用
dfs或bfs的思想来进行遍历; - 使用used数组来表示当前位置是否被访问过。
3. 代码实现(DFS)
class Solution {
public:bool canReach(vector<int>& arr, int start) {int n = arr.size();vector<bool> used(n, false);function<bool(int)> dfs = [&](int idx) {if (idx < 0 || idx >= n))return false;if(used[idx])return false;if (arr[idx] == 0)return true;used[idx] = true;return dfs(idx - arr[idx]) || dfs(idx + arr[idx]);};return dfs(start);}
};
4. 代码实现(BFS)
class Solution {
public:bool canReach(vector<int>& arr, int start) {int n = arr.size();vector<bool> used(n, false);queue<int> que;que.push(start);while (!que.empty()) {auto it = que.front();que.pop();// 下标超出范围if (it < 0 || it >= n)continue;// 当前位置下标已访问过if (used[it])continue;if (arr[it] == 0)return true;used[it] = true;que.push(it + arr[it]);que.push(it - arr[it]);}return false;}
};