当前位置: 首页 > 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;从而达…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...

简单介绍C++中 string与wstring

在C中&#xff0c;string和wstring是两种用于处理不同字符编码的字符串类型&#xff0c;分别基于char和wchar_t字符类型。以下是它们的详细说明和对比&#xff1a; 1. 基础定义 string 类型&#xff1a;std::string 字符类型&#xff1a;char&#xff08;通常为8位&#xff09…...