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

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

yaml读取写入常见错误 (‘cannot represent an object‘, 117)

错误一&#xff1a;yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因&#xff0c;后面把yaml.safe_dump直接替换成yaml.dump&#xff0c;确实能保存&#xff0c;但出现乱码&#xff1a; 放弃yaml.dump&#xff0c;又切…...

STL 2迭代器

文章目录 1.迭代器2.输入迭代器3.输出迭代器1.插入迭代器 4.前向迭代器5.双向迭代器6.随机访问迭代器7.不同容器返回的迭代器类型1.输入 / 输出迭代器2.前向迭代器3.双向迭代器4.随机访问迭代器5.特殊迭代器适配器6.为什么 unordered_set 只提供前向迭代器&#xff1f; 1.迭代器…...