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

代码随想录算法训练营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) 深度优先搜索&#xff0c;和之前的回溯题类似。 #include <iostream> #include <vector> using namespace std;// 定义一个二维向量来存储所有可能的路径 vector<vector<int>> paths; // 定义一个向…...

DNF手游鬼剑士攻略:全面解析流光星陨刀的获取与升级!云手机强力辅助!

《地下城与勇士》&#xff08;DNF&#xff09;手游是一款广受欢迎的多人在线角色扮演游戏&#xff0c;其中鬼剑士作为一个经典职业&#xff0c;因其强大的输出能力和炫酷的技能特效&#xff0c;吸引了众多玩家的青睐。在这篇攻略中&#xff0c;我们将详细介绍鬼剑士的一把重要武…...

npm创建一个空的vue3项目的方法或者pnpm创建vue3项目

1、前提我们已经安装了npm&#xff0c;或者pnpm 2、我们用npm来创建vue3项目 快速上手 | Vue.js 官网地址 这里我安装是的 node v18.20.3 以下是安装过程 &#xff1a; npm create vuelatest 根据自己的需要进行创建即可。 3、我们用pnpm来创建vite vue3项目 pnpm create …...

LSH算法:高效相似性搜索的原理与Python实现I

局部敏感哈希&#xff08;LSH&#xff09;技术是快速近似最近邻&#xff08;ANN&#xff09;搜索中的一个关键方法&#xff0c;广泛应用于实现高效且准确的相似性搜索。这项技术对于许多全球知名的大型科技公司来说是不可或缺的&#xff0c;包括谷歌、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 是一个强大的开源库&#xff0c;专门用于处理和可视化3D数据&#xff0c;如点云、网格和…...

无法下载 https://mirrors./ubuntu/dists/bionic/main/binary-arm64/Packages

ubuntu系统执行sudo apt update命令的时候&#xff0c;遇到如下问题&#xff1a; 忽略: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版&#xff0c;基于JavaVueUni-app开发&#xff0c;在微信公众号、小程序、H5移动端都能使用&#xff0c;代码全开源无加密&#xff0c;独立部署&#xff0c;二开很方便&#xff0c;还支持免费商用&#xff0c;能满足企业新零售、分销推广、拼团、砍价、…...

【开发环境】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等命令行工具打开后&#xff0c;输入上面的命令 之后根据中文提示完成Homebrew的下载…...

Flask-Session使用Redis

Flask-Session使用Redis 一、介绍 在Flask中&#xff0c;session数据默认是以加密的cookie形式存储在用户的浏览器中的。但是&#xff0c;真正的session数据应该存储在服务器端。Django框架会将session数据存储在数据库的djangosession表中&#xff0c;而Flask则可以通过第三…...

Redis缓存管理机制

在当今快节奏的数字世界中&#xff0c;性能优化对于提供无缝的用户体验至关重要。缓存在提高应用程序性能方面发挥着至关重要的作用&#xff0c;它通过将经常使用或处理的数据存储在临时高速存储中来减少数据库负载并缩短响应时间&#xff0c;从而减少系统的延迟。Redis 是一种…...

初学嵌入式是弄linux还是单片机?

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“666”之后私信回复“666”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01;1、先入门了51先学了89c52…...

【基础算法总结】分治—快排

分治—快排 1.分治2.颜色分类3.排序数组4.数组中的第K个最大元素5.库存管理 III 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 1.分治 分治…...

[C++]——同步异步日志系统(1)

同步异步日志系统 一、项⽬介绍二、开发环境三、核心技术四、环境搭建五、日志系统介绍5.1 为什么需要日志系统5.2 日志系统技术实现5.2.1 同步写日志5.2.2 异步写日志 日志系统&#xff1a; 日志&#xff1a;程序在运行过程中&#xff0c;用来记录程序运行状态信息。 作用&…...

python 第6册 辅助excel 002 批量创建非空白的 Excel 文件

---用教授的方式学习 此案例主要通过使用 while 循环以及 openpyxl. load_workbook()方法和 Workbook 的 save()方法&#xff0c;从而实现在当前目录中根据已经存在的Excel 文件批量创建多个非空白的Excel 文件。当运行此案例的Python 代码&#xff08;A002.py 文件&#xff0…...

力扣61. 旋转链表(java)

思路&#xff1a;用快慢指针找到最后链表k个需要移动的节点&#xff0c;然后中间断开节点&#xff0c;原尾节点连接原头节点&#xff0c;返回新的节点即可&#xff1b; 但因为k可能比节点数大&#xff0c;所以需要先统计节点个数&#xff0c;再取模&#xff0c;看看k到底需要移…...

智慧园区综合平台解决方案PPT(75页)

## 智慧园区的理解 ### 从园区1.0到园区4.0的演进 1. 园区1.0&#xff1a;以土地经营为主&#xff0c;成本驱动&#xff0c;提供基本服务。 2. 园区2.0&#xff1a;服务驱动&#xff0c;关注企业成长&#xff0c;提供增值服务。 3. 园区3.0&#xff1a;智慧型园区&#xff…...

Python只读取Excel文件的一部分数据,比如特定范围的行和列?

如何只读取Excel文件的一部分数据&#xff0c;比如特定范围的行和列&#xff1f; 在Python中&#xff0c;如果你只想读取Excel文件的特定范围&#xff0c;可以使用以下方法&#xff1a; pandas: Pandas是一个强大的数据处理库&#xff0c;它有一个内置函数read_excel()用于读…...

快速入门FreeRTOS心得(正点原子学习版)

对于FreeROTS&#xff0c;我第一反应想到的就是通信里的TDM&#xff08;时分多址&#xff09;。不同任务给予分配不同的时间间隔&#xff0c;也就是任务之间在每个timeslot都在来回切换。 这里有重要的一点&#xff0c;就是中断要短小&#xff0c;优先级是自高到底进行打断。 …...

【博主推荐】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 源代码 源码下载万套模板&#xff0c;程序开发&#xff0c;在线开发&#xff0c…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...