为什么要做网站优化,网站的网络营销推广方案,网站 建设,wordpress设置固定链接和伪静态今日份题目#xff1a;
这里有一个非负整数数组 arr#xff0c;你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时#xff0c;你可以跳到 i arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 **任一** 下标处。
注意#xff0c;不管是什…今日份题目
这里有一个非负整数数组 arr你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时你可以跳到 i arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 **任一** 下标处。
注意不管是什么情况下你都无法跳到数组之外。
示例1 输入arr [4,2,3,0,3,1,2], start 5 输出true 解释 到达值为 0 的下标 3 有以下可能方案 下标 5 - 下标 4 - 下标 1 - 下标 3 下标 5 - 下标 6 - 下标 4 - 下标 1 - 下标 3
示例2 输入arr [4,2,3,0,3,1,2], start 0 输出true 解释 到达值为 0 的下标 3 有以下可能方案 下标 0 - 下标 4 - 下标 1 - 下标 3
示例3 输入arr [3,0,2,1,2], start 2 输出false 解释无法到达值为 0 的下标 1 处。
提示
- 1 arr.length 5 * 10^4 - 0 arr[i] arr.length - 0 start arr.length
题目思路
转移规则就是下一个位置可以跳到 iarr[i] 或 i-arr[i] 我们考虑搜索图中信息看搜索过程中能否途径存放着0的位置。我们使用bfs广度优先遍历每次从队列中取出一个位置然后根据转移规则判断将不是存放着0的位置信息放入队列当中直到队列为空。如果到过放着0的位置就返回true否则就返回false。
代码
class Solution
{
public:bool canReach(vectorint arr, int start) {if (arr[start]0) return true;int narr.size();bool visited[100000]{false}; //用于标记到达过queueint p;p.push(start);visited[start]true;//bfswhile(!p.empty()) {int curp.front();p.pop();//iarr[i]的情况if(curarr[cur]0curarr[cur]nvisited[curarr[cur]]false) {if(arr[curarr[cur]]0) return true; //到达终点返回true//否则还未到终点继续压入队列进行bfsp.push(curarr[cur]);visited[curarr[cur]]true;}//i-arr[i]的情况if(cur-arr[cur]0cur-arr[cur]n!visited[cur-arr[cur]]) {if(arr[cur-arr[cur]]0) return true; //到达终点返回true//还未到终点继续bfsp.push(cur-arr[cur]);visited[cur-arr[cur]]true;}}//bfs遍历完还没到达终点返回falsereturn false;}
};提交结果 欢迎大家在评论区讨论如有不懂的部分欢迎在评论区留言
更新不易宝子们点个赞支持下谢谢 每天一道leetcode大家一起在评论区打卡呀
