代码随想录算法训练营Day56|所有可达路径、797.所有可能的路径
所有可达路径
98. 所有可达路径 (kamacoder.com)
深度优先搜索,和之前的回溯题类似。
#include <iostream>
#include <vector>
using namespace std;// 定义一个二维向量来存储所有可能的路径
vector<vector<int>> paths;
// 定义一个向量来存储当前路径
vector<int> path;// 定义深度优先搜索函数
void dfs(const vector<vector<int>>& graph, int x, int n) {// 如果到达节点n,将当前路径添加到所有路径中if (x == n) {paths.push_back(path);return;}// 遍历所有可能的下一个节点for (int i = 1; i <= n; i++) {// 如果节点x和节点i之间有边(即连通)if (graph[x][i] == 1) {// 将节点i添加到当前路径path.push_back(i);// 递归地继续搜索从节点i开始的路径dfs(graph, i, n);// 回溯,移除节点i,尝试其他可能的路径path.pop_back();}}
}int main() {int N, M; // N表示节点数量,M表示边的数量cin >> N >> M; // 输入节点数量和边的数量// 创建一个(N+1) x (N+1)的二维向量,初始化所有值为0vector<vector<int>> graph(N + 1, vector<int>(N + 1, 0));int s, t;while (M--) { // 循环M次,输入每条边的两个节点cin >> s >> t;graph[s][t] = 1; // 表示节点s和节点t之间有边,即连通}// 从节点1开始搜索,将节点1添加到当前路径path.push_back(1);dfs(graph, 1, N); // 调用DFS函数搜索所有路径// 如果没有找到路径,输出-1if (paths.size() == 0)cout << -1 << endl;// 输出所有找到的路径for (auto x : paths) {for (int i = 0; i < x.size() - 1; i++) {cout << x[i] << " ";}cout << x[x.size() - 1] << endl;}
}
在构建图是,读入所有边,时间复杂度为O(M),在DFS是,最坏情况需要访问图中的每个节点和每天便,DFS的时间复杂度为O(N+M)。总的时间复杂度为O(N+M)。
空间复杂度,用邻接矩阵来存储graph信息需要(N+1)^2(从0到N+1的矩阵),paths在图全连接的情况下,可能要存储2^(N-1)条路(1-N),path为O(N),空间复杂度为O(2^(N-1))。
邻接链表参考
代码随想录 (programmercarl.com)
邻接数组也可以自己写写看。
所有可能的路径
797. 所有可能的路径 - 力扣(LeetCode)
上题的核心代码,代码如下,分析基本和上题相同。
class Solution {
public:// 定义一个向量来存储当前路径vector<int> path;// 定义一个二维向量来存储所有可能的路径vector<vector<int>> paths;// 定义深度优先搜索函数void dfs(const vector<vector<int>>& graph, int x, int n) {// 如果到达目标节点n,将当前路径添加到所有路径中if (x == n) {paths.push_back(path);return;}// 遍历当前节点的所有相邻节点for (int i = 0; i < graph[x].size(); i++) {// 将相邻节点添加到当前路径path.push_back(graph[x][i]);// 递归地继续搜索从相邻节点开始的路径dfs(graph, graph[x][i], n);// 回溯,移除刚刚添加的节点,以便尝试其他路径path.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {// 目标节点是图的最后一个节点 graph.size() - 1int n = graph.size() - 1;// 从源节点0开始,将源节点添加到当前路径path.push_back(0);// 调用DFS函数搜索所有路径dfs(graph, 0, n);// 返回找到的所有路径return paths;}
};
相关文章:
代码随想录算法训练营Day56|所有可达路径、797.所有可能的路径
所有可达路径 98. 所有可达路径 (kamacoder.com) 深度优先搜索,和之前的回溯题类似。 #include <iostream> #include <vector> using namespace std;// 定义一个二维向量来存储所有可能的路径 vector<vector<int>> paths; // 定义一个向…...
DNF手游鬼剑士攻略:全面解析流光星陨刀的获取与升级!云手机强力辅助!
《地下城与勇士》(DNF)手游是一款广受欢迎的多人在线角色扮演游戏,其中鬼剑士作为一个经典职业,因其强大的输出能力和炫酷的技能特效,吸引了众多玩家的青睐。在这篇攻略中,我们将详细介绍鬼剑士的一把重要武…...
npm创建一个空的vue3项目的方法或者pnpm创建vue3项目
1、前提我们已经安装了npm,或者pnpm 2、我们用npm来创建vue3项目 快速上手 | Vue.js 官网地址 这里我安装是的 node v18.20.3 以下是安装过程 : npm create vuelatest 根据自己的需要进行创建即可。 3、我们用pnpm来创建vite vue3项目 pnpm create …...
LSH算法:高效相似性搜索的原理与Python实现I
局部敏感哈希(LSH)技术是快速近似最近邻(ANN)搜索中的一个关键方法,广泛应用于实现高效且准确的相似性搜索。这项技术对于许多全球知名的大型科技公司来说是不可或缺的,包括谷歌、Netflix、亚马逊、Spotify…...
cesium 添加 Echarts图层(人口迁徒图)
cesium 添加 Echarts 人口迁徒图(下面附有源码) 1、实现思路 1、在scene上面新增一个canvas画布 2、通坐标转换,将经纬度坐标转为屏幕坐标来实现 3、将ecarts 中每个series数组中元素都加 coordinateSystem: ‘cesiumEcharts’ 2、示例代码 <!DOCTYPE html> <ht…...
Windows下快速安装Open3D-0.18.0(python版本)详细教程
目录 一、Open3D简介 1.1主要用途 1.2应用领域 二、安装Open3D 2.1 激活环境 2.2 安装open3d 2.3测试安装是否成功 三、测试代码 3.1 代码 3.2 显示效果 一、Open3D简介 Open3D 是一个强大的开源库,专门用于处理和可视化3D数据,如点云、网格和…...
无法下载 https://mirrors./ubuntu/dists/bionic/main/binary-arm64/Packages
ubuntu系统执行sudo apt update命令的时候,遇到如下问题: 忽略:82 https://mirrors.tuna.tsinghua.edu.cn/ubuntu bionic-backports/universe arm64 Packages 错误:81 https://mirrors.tuna.tsinghua.edu.cn/ubuntu bionic-backports/main arm64 Packa…...
最新CRMEB商城多商户java版源码v1.6版本+前端uniapp
CRMEB 开源商城系统Java版,基于JavaVueUni-app开发,在微信公众号、小程序、H5移动端都能使用,代码全开源无加密,独立部署,二开很方便,还支持免费商用,能满足企业新零售、分销推广、拼团、砍价、…...
【开发环境】MacBook M2安装git并拉取gitlab项目,解决gitlab出现Access Token使用无效的方法
文章目录 安装Homebrew安装git打开IDEA配置git打开IDEA拉取项目 安装Homebrew /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"在iTerm等命令行工具打开后,输入上面的命令 之后根据中文提示完成Homebrew的下载…...
Flask-Session使用Redis
Flask-Session使用Redis 一、介绍 在Flask中,session数据默认是以加密的cookie形式存储在用户的浏览器中的。但是,真正的session数据应该存储在服务器端。Django框架会将session数据存储在数据库的djangosession表中,而Flask则可以通过第三…...
Redis缓存管理机制
在当今快节奏的数字世界中,性能优化对于提供无缝的用户体验至关重要。缓存在提高应用程序性能方面发挥着至关重要的作用,它通过将经常使用或处理的数据存储在临时高速存储中来减少数据库负载并缩短响应时间,从而减少系统的延迟。Redis 是一种…...
初学嵌入式是弄linux还是单片机?
在开始前刚好我有一些资料,是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」, 点个关注在评论区回复“666”之后私信回复“666”,全部无偿共享给大家!!!1、先入门了51先学了89c52…...
【基础算法总结】分治—快排
分治—快排 1.分治2.颜色分类3.排序数组4.数组中的第K个最大元素5.库存管理 III 点赞👍👍收藏🌟🌟关注💖💖 你的支持是对我最大的鼓励,我们一起努力吧!😃😃 1.分治 分治…...
[C++]——同步异步日志系统(1)
同步异步日志系统 一、项⽬介绍二、开发环境三、核心技术四、环境搭建五、日志系统介绍5.1 为什么需要日志系统5.2 日志系统技术实现5.2.1 同步写日志5.2.2 异步写日志 日志系统: 日志:程序在运行过程中,用来记录程序运行状态信息。 作用&…...
python 第6册 辅助excel 002 批量创建非空白的 Excel 文件
---用教授的方式学习 此案例主要通过使用 while 循环以及 openpyxl. load_workbook()方法和 Workbook 的 save()方法,从而实现在当前目录中根据已经存在的Excel 文件批量创建多个非空白的Excel 文件。当运行此案例的Python 代码(A002.py 文件࿰…...
力扣61. 旋转链表(java)
思路:用快慢指针找到最后链表k个需要移动的节点,然后中间断开节点,原尾节点连接原头节点,返回新的节点即可; 但因为k可能比节点数大,所以需要先统计节点个数,再取模,看看k到底需要移…...
智慧园区综合平台解决方案PPT(75页)
## 智慧园区的理解 ### 从园区1.0到园区4.0的演进 1. 园区1.0:以土地经营为主,成本驱动,提供基本服务。 2. 园区2.0:服务驱动,关注企业成长,提供增值服务。 3. 园区3.0:智慧型园区ÿ…...
Python只读取Excel文件的一部分数据,比如特定范围的行和列?
如何只读取Excel文件的一部分数据,比如特定范围的行和列? 在Python中,如果你只想读取Excel文件的特定范围,可以使用以下方法: pandas: Pandas是一个强大的数据处理库,它有一个内置函数read_excel()用于读…...
快速入门FreeRTOS心得(正点原子学习版)
对于FreeROTS,我第一反应想到的就是通信里的TDM(时分多址)。不同任务给予分配不同的时间间隔,也就是任务之间在每个timeslot都在来回切换。 这里有重要的一点,就是中断要短小,优先级是自高到底进行打断。 …...
【博主推荐】HTML5实现简洁好看的个人简历网页模板源码
文章目录 1.设计来源1.1 主界面1.2 关于我界面1.3 工作经验界面1.4 学习教育界面1.5 个人技能界面1.6 专业特长界面1.7 朋友评价界面1.8 获奖情况界面1.9 联系我界面 2.效果和源码2.1 动态效果2.2 源代码 源码下载万套模板,程序开发,在线开发,…...
Android应用安装过程
Android 系统源码源码-应用安装过程 Android 中应用安装的过程就是解析 AndroidManifest.xml 的过程,系统可以从 Manifest 中得到应用程序的相关信息,比如 Activity、Service、Broadcast Receiver 和 ContentProvider 等。这些工作都是由 PackageManage…...
Word中输入文字时,后面的文字消失
当在Word中输入文字时,如果发现后面的文字消失,通常是由以下3个原因造成的: 检查Insert键状态:首先确认是否误按了Insert键。如果是,请再次按下Insert键以切换回插入模式。在插入模式下,新输入的文字会插入…...
【LeetCode】合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路 水题,主要用于后面的链表的归并排序做了该题 AC代码 # Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nex…...
分子AI预测赛Task1笔记
分子AI预测赛Task1笔记 实践步骤:跑通baseline → 尝试个人idea→尝试进阶baseline 一、跑通baseline 1、应当先下载数据库 下载相应的数据库 !pip install lightgbm openpyxl2、训练模型并预测结果 首先要导入相应的库和方法类,如pandas等 # 1. …...
ubuntu 安装并启用 samba
环境:ubuntu server 24.04 步骤如下: sudo apt update sudo apt install samba修改配置文件: sudo vi /etc/samba/smb.conf新增内容: [username]path /home/[username]available yesvalid users [username]read only nobrow…...
atcoder ABC 357-D题详解
atcoder ABC 357-D题详解 Problem Statement For a positive integer N, let VN be the integer formed by concatenating N exactly N times. More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get VN. For…...
从单一到多元:EasyCVR流媒体视频汇聚技术推动安防监控智能升级
随着科技的飞速发展,视频已成为我们日常生活和工作中的重要组成部分。尤其在远程办公、在线教育、虚拟会议等领域,视频的应用愈发广泛。为了满足日益增长的视频需求,流媒体视频汇聚融合技术应运而生,它不仅改变了传统视频的观看和…...
Spring MVC数据绑定和响应——数据回写(二)JSON数据的回写
项目中已经导入了Jackson依赖,可以先调用Jackson的JSON转换的相关方法,将对象或集合转换成JSON数据,然后通过HttpServletResponse将JSON数据写入到输出流中完成回写,具体步骤如下。 1、修改文件DataController.java,在…...
怎么快速给他人分享图片?扫描二维码看图的简单做法
现在通过二维码来查看图片是一种很常见的方法,通过二维码来查看图片不仅能够减少对手机存储空间的占用,而且获取图片变得更加方便快捷,只需要扫码就能够查看图片,有利于图片的展现。很多的场景中都有图片二维码的应用,…...
【UML用户指南】-26-对高级行为建模-状态图
目录 1、概念 2、组成结构 3、一般用法 4、常用建模技术 4.1、对反应型对象建模 一个状态图显示了一个状态机。在为对象的生命期建模中 活动图展示的是跨过不同的对象从活动到活动的控制流 状态图展示的是单个对象内从状态到状态的控制流。 在UML中,用状态图…...
解决VSCode无法用ssh连接远程服务器的问题
原因: 因为windows自带的ssh无法连接远程服务器,需要用git底下的ssh.exe。 搜了很久,试过很多方法,包括替换掉环境变量中的ssh,但是都无效,最后发现是要在VSCode中配置需要使用哪个ssh.exe。 步骤&#…...
【区块链+基础设施】银联云区块链服务 | FISCO BCOS应用案例
为了顺应区块链基础设施化的发展趋势,中国银联推出了银联云区块链服务——UPBaaS,为金融行业采用区块链 技术提出了解决方案,微众银行为平台提供 FISCO BCOS 区块链开源技术支持。通过银联云区块链服务,用户可 以用可视化的方式创…...
Java SE入门及基础(61) 死锁 死锁发生条件
目录 死锁 1. 死锁的概念 2. 死锁发生条件 互斥条件 不可剥夺条件 请求与保持条件 循环等待 3. 案例分析 示例 分析 死锁 1. 死锁的概念 Deadlock describes a situation where two or more threads are blocked forever, waiting for each other 死锁描述了一种情…...
简单爬虫案例——爬取快手视频
网址:aHR0cHM6Ly93d3cua3VhaXNob3UuY29tL3NlYXJjaC92aWRlbz9zZWFyY2hLZXk9JUU2JThCJTg5JUU5JTlEJUEy 找到视频接口: 视频链接在photourl中 完整代码: import requestsimport re url https://www.kuaishou.com/graphql cookies {did: web_…...
42、nginx之nginx.conf
nginx----web服务器 一、nginx http就是apache,在国内很少。 nginx是开源的,是一款高性能,轻量级的web服务软件。 稳定性高,而且版本迭代比较快(修复bug速度比较快,安全性快) 消耗系统资源…...
高薪程序员必修课-java为什么要用并发编程
目录 前言 1. 提高性能和效率 2. 更好地响应用户 3. 优化I/O操作 具体示例 示例1:提高性能和效率 示例2:更好地响应用户 示例3:优化I/O操作 总结 前言 并发编程允许多个线程在同一时间执行任务。下面我们从多个原理角度来解释为什么J…...
postgreSQL学习
postgreSql学习 学习参考:1、命令1.1 登录1.2 关闭连接 2、常用数据类型2.1 数值类型2.2 字符串类型2.3 时间2.4 其他 3、自增主键4、sql4.1 库操作(1)创建新库(2)切换数据库(3)删库【谨慎&…...
【3】系统标定
文章目录 雷达标定相机主雷达标定底盘动力学标定车辆循迹验证建图 雷达标定 主要是为了获得到lidar到imu的tf关系。imu为父坐标lidar为子坐标。其他雷达标定到主lidar坐标系下。 标定的结果都是生成一个是四元数。 #mermaid-svg-crOWRnT4UE0jtJVy {font-family:"trebuch…...
网安小贴士(3)网安协议
一、前言 网络安全协议是构建安全网络环境的基础,它们帮助保护网络通信免受各种威胁和攻击。 二、定义 网络安全协议是指在计算机网络中用于确保网络通信和数据传输安全的协议。它们定义了在网络通信过程中的安全机制、加密算法、认证和授权流程等,以保…...
大数据面试题之HBase(1)
目录 介绍下HBase HBase优缺点 说下HBase原理 介绍下HBase架构 HBase读写数据流程 HBase的读写缓存 在删除HBase中的一个数据的时候,它什么时候真正的进行删除呢?当你进行删除操作,它是立马就把数据删除掉了吗? HBase中的二级索引 HBa…...
git回退commit的方式
在Git中,回退commit(即撤销之前的提交)可以通过多种方式来实现。以下是一些常见的方法,以及它们的详细步骤和注意事项: ### 1. 使用git revert命令 git revert命令用于撤销某次commit,但它并不会删除该comm…...
[Information Sciences 2023]用于假新闻检测的相似性感知多模态提示学习
推荐的一个视频:p-tuning P-tunning直接使用连续空间搜索 做法就是直接将在自然语言中存在的词直接替换成可以直接训练的输入向量。本身的Pretrained LLMs 可以Fine-Tuning也可以不做。 这篇论文也解释了为什么很少在其他领域结合知识图谱的原因:就是因…...
自定义vue3 hooks
文章目录 hooks目录结构demo hooks 当页面内有很多的功能,js代码太多,不好维护,可以每个功能都有写一个js或者ts,这样的话,代码易读,并且容易维护,组合式setup写法与此结合👍&#…...
《昇思25天学习打卡营第21天 | 昇思MindSporePix2Pix实现图像转换》
21天 本节学习了通过Pix2Pix实现图像转换。 Pix2Pix是基于条件生成对抗网络(cGAN)实现的一种深度学习图像转换模型。可以实现语义/标签到真实图片、灰度图到彩色图、航空图到地图、白天到黑夜、线稿图到实物图的转换。Pix2Pix是将cGAN应用于有监督的图…...
【文档+源码+调试讲解】科研经费管理系统
目 录 目 录 摘 要 ABSTRACT 1 绪论 1.1 课题背景 1.2 研究现状 1.3 研究内容 2 系统开发环境 2.1 vue技术 2.2 JAVA技术 2.3 MYSQL数据库 2.4 B/S结构 2.5 SSM框架技术 3 系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2 操作可行性 3.1.3 经济可行性 3.1…...
linux 下 rm 为什么要这么写?
下面代码中的rm 为什么要写成/bin/rm? 大文件清理,高宿主含量样本可节约>90%空间/bin/rm -rf temp/qc/*contam* temp/qc/*unmatched* temp/qc/*.fqls -l temp/qc/ 这是一个很好的问题,观察很仔细, 也带着了自己的思考。 rm是 Linux 下的一个危险…...
【Spring Boot】Spring AOP中的环绕通知
目录 一、什么是AOP?二、AOP 的环绕通知2.1 切点以及切点表达式2.2 连接点2.3 通知(Advice)2.4 切面(Aspect)2.5 不同通知类型的区别2.5.1 正常情况下2.5.2异常情况下 2.6 统一管理切点PointCut 一、什么是AOP? Aspect Oriented Programmingÿ…...
docker部署前端,配置域名和ssl
之前使用80端口部署前端项目后,可以使用IP端口号在公网访问到部署的项目。 进行ICP域名备案后,可以通过域名解析将IP套壳,访问域名直接访问到部署的项目~ 如果使用http协议可以很容易实现这个需求,对nginx.conf文件进行修改&#…...
初学Spring之 IOC 控制反转
Spring 是一个轻量级的控制反转(IOC)和面向切面编程(AOP)的框架 导入 jar 包:spring-webmvc、spring-jdbc <dependency><groupId>org.springframework</groupId><artifactId>spring-webmvc&…...
rpc的仅有通信的功能,在网断的情况下,比网通情况下,内存增长会是什么原因
RPC(Remote Procedure Call,远程过程调用)主要负责在分布式系统中透明地调用远程服务,就像调用本地函数一样。它封装了网络通信的细节,使得开发者可以专注于业务逻辑而非底层通信协议。RPC通信通常包括序列化、网络传输…...