当前位置: 首页 > news >正文

每天一道leetcode:1306. 跳跃游戏 III(图论中等广度优先遍历)

今日份题目:

这里有一个非负整数数组 `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`

题目思路

转移规则就是下一个位置可以跳到 i+arr[i] 或 i-arr[i] ,我们考虑搜索图中信息看搜索过程中能否途径存放着0的位置。我们使用bfs广度优先遍历,每次从队列中取出一个位置,然后根据转移规则判断,将不是存放着0的位置信息放入队列当中,直到队列为空。如果到过放着0的位置就返回true,否则就返回false。

代码

class Solution 
{
public:bool canReach(vector<int>& arr, int start) {if (arr[start]==0) return true;int n=arr.size();bool visited[100000]={false}; //用于标记到达过queue<int> p;p.push(start);visited[start]=true;//bfswhile(!p.empty()) {int cur=p.front();p.pop();//i+arr[i]的情况if(cur+arr[cur]>=0&&cur+arr[cur]<n&&visited[cur+arr[cur]]==false) {if(arr[cur+arr[cur]]==0) return true; //到达终点,返回true//否则还未到终点,继续压入队列进行bfsp.push(cur+arr[cur]);visited[cur+arr[cur]]=true;}//i-arr[i]的情况if(cur-arr[cur]>=0&&cur-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,大家一起在评论区打卡呀!

相关文章:

每天一道leetcode:1306. 跳跃游戏 III(图论中等广度优先遍历)

今日份题目&#xff1a; 这里有一个非负整数数组 arr&#xff0c;你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时&#xff0c;你可以跳到 i arr[i] 或者 i - arr[i]。 请你判断自己是否能够跳到对应元素值为 0 的 **任一** 下标处。 注意&#xff0c;不管是什…...

76参考链接

参考链接 官方文件综合介绍[let 和 const](https://es6.ruanyifeng.com/#docs/reference#let 和 const)解构赋值字符串正则数值数组函数对象Symbol[Set 和 Map](https://es6.ruanyifeng.com/#docs/reference#Set 和 Map)[Proxy 和 Reflect](https://es6.ruanyifeng.com/#docs/…...

浅析Linux SCSI子系统:调试方法

文章目录 SCSI日志调试功能scsi_logging_level调整SCSI日志等级 SCSI trace events使能SCSI trace events方式一&#xff1a;通过set_event接口方式二&#xff1a;通过enable 跟踪trace信息 相关参考 SCSI日志调试功能 SCSI子系统支持内核选项CONFIG_SCSI_LOGGING配置日志调试…...

【Unity3D】水面特效

1 前言 水波特效 中通过屏幕后处理实现了环形水波效果&#xff0c;本文通过 Shader Graph 实现了模拟水面特效&#xff0c;包含以下特效细节。 深水区和浅水区颜色差异&#xff1b;水面有波纹&#xff0c;并且在移动&#xff1b;水面起伏波动&#xff1b;水面边缘有水泡&#…...

CSS中的flex布局详细讲解

Flex 布局 Flex 布局是一种现代的 CSS 布局模型&#xff0c;用于实现灵活的盒子布局。它提供了强大的布局能力&#xff0c;使得元素可以自动调整大小、对齐和分布&#xff0c;适用于构建响应式和可伸缩的布局。 Flex 布局使用 flex 容器和 flex 项目的概念。容器是一个父元素…...

Python功能制作之简单的音乐播放器

需要导入的库&#xff1a; pip install PyQt5 源码&#xff1a; import os from PyQt5.QtCore import Qt, QUrl from PyQt5.QtGui import QIcon, QPixmap from PyQt5.QtMultimedia import QMediaPlayer, QMediaContent from PyQt5.QtWidgets import QApplication, QMainWind…...

GAN生成对抗模型根据minist数据集生成手写数字图片

文章目录 1.项目介绍2相关网站3具体的代码及结果导入工具包设置超参数定义优化器&#xff0c;以及损失函数训练时的迭代过程训练结果的展示 1.项目介绍 通过用minist数据集进行训练&#xff0c;得到一个GAN模型&#xff0c;可以生成与minist数据集类似的图片。 GAN是一种生成模…...

【K8S源码之Pod漂移】整体概况分析 controller-manager 中的 nodelifecycle controller(Pod的驱逐)

参考 k8s 污点驱逐详解-源码分析 - 掘金 k8s驱逐篇(5)-kube-controller-manager驱逐 - 良凯尔 - 博客园 k8s驱逐篇(6)-kube-controller-manager驱逐-NodeLifecycleController源码分析 - 良凯尔 - 博客园 k8s驱逐篇(7)-kube-controller-manager驱逐-taintManager源码分析 - 良…...

[保研/考研机试] KY212 二叉树遍历 华中科技大学复试上机题 C++实现

题目链接&#xff1a; 二叉树遍历_牛客题霸_牛客网二叉树的前序、中序、后序遍历的定义&#xff1a; 前序遍历&#xff1a;对任一子树&#xff0c;先访问根&#xff0c;然后遍历其左子树&#xff0c;最。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/43719512169…...

CSS笔记

介绍 CSS导入方式 三种方法都将文字设置成了红色 CSS选择器 元素选择器 id选择器 图中div将颜色控制为红色&#xff0c;#name将颜色控制为蓝色&#xff0c;谁控制的范围最小&#xff0c;谁就生效&#xff0c;所以第二个div是蓝色的。id属性值要唯一&#xff0c;否则报错。 clas…...

链栈Link-Stack

0、节点结构体定义 typedef struct SNode{int data;struct SNode *next; } SNode, *LinkStack; 1、初始化 bool InitStack(LinkStack &S) //S为栈顶指针&#xff08;存数据的头节点&#xff09; {S NULL;return true; } 2、入栈 bool Push(LinkStack &S, int e) {…...

Ubuntu 20系统WIFI设置静态IP地址,以及断连问题

​最近工作需要购置了一台GPU机器&#xff0c;然后搭建了深度学习的运行环境&#xff0c;在工作中将这台机器当做深度学习的服务器来使用&#xff0c;前期已经配置好多用户以及基础环境。但最近通过xshell连接总是不间断的出现断连现象。 补充一点&#xff0c;Ubuntu系统中与网…...

(一)idea连接GitHub的全部流程(注册GitHub、idea集成GitHub、增加合作伙伴、跨团队合作、分支操作)

&#xff08;二&#xff09;Git在公司中团队内合作和跨团队合作和分支操作的全部流程&#xff08;一篇就够&#xff09;https://blog.csdn.net/m0_65992672/article/details/132336481 4.1、简介 Git是一个免费的、开源的*分布式**版本控制**系统*&#xff0c;可以快速高效地…...

-bash: java: command not found笔记

文章目录 场景解决方案找java的方法find命令进行查找根据java进程找寻具体位置 场景 linux系统执行java命令时报错&#xff1a; -bash: java: command not found。 解决方案 可能是没有安装java(这种情况比较少)或者安装了java但是没有设置环境变量(一般是这种情况)。 找ja…...

C++ typename and .template

https://makecleanandmake.com/2015/07/20/leading-typename-dot-template-and-why-they-are-necessary/ typename Obj<T>::type var;v.template m<int>();...

uniapp,使用canvas制作一个签名版

先看效果图 我把这个做成了页面&#xff0c;没有做成组件&#xff0c;因为之前我是配合uview-plus的popup弹出层使用的&#xff0c;这种组件好像是没有生命周期的&#xff0c;第一次打开弹出层可以正常写字&#xff0c;但是关闭之后再打开就不会显示绘制的线条了&#xff0c;还…...

【大数据】Flink 详解(五):核心篇 Ⅳ

Flink 详解&#xff08;五&#xff09;&#xff1a;核心篇 Ⅳ 45、Flink 广播机制了解吗&#xff1f; 从图中可以理解 广播 就是一个公共的共享变量&#xff0c;广播变量存于 TaskManager 的内存中&#xff0c;所以广播变量不应该太大&#xff0c;将一个数据集广播后&#xff0…...

设计模式-建造者模式

核心思想 抽取共同的行为&#xff0c;允许使用者指定复杂对象的类型和内容&#xff0c;不需要了解内部的构建细节使用多个简单的行为构建一个复杂的对象&#xff0c;将对象的构建过程和它的表示分离&#xff0c;同样的构建过程可以创建不同的表示 优缺点 优点 使用者不需要知…...

flutter 设置app图标

使用插件 flutter_launcher_icons 在 pubspec.yaml 配置文件中 加入 dev_dependencies dev_dependencies: flutter_launcher_icons: "^0.13.1" 准备好app得 icon 图标 其中icon的名字为icon.png 创建assets文件夹 和子文件夹icon iamge 配置静态资源路径 完整配置…...

守护网络安全:深入了解DDOS攻击防护手段

ddos攻击防护手段有哪些?在数字化快速发展的时代&#xff0c;网络安全问题日益凸显&#xff0c;其中分布式拒绝服务(DDOS)攻击尤为引人关注。这种攻击通过向目标网站或服务器发送大量合法或非法的请求&#xff0c;旨在使目标资源无法正常处理其他用户的请求&#xff0c;从而达…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...