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

Day 55 卡玛笔记

这是基于代码随想录的每日打卡

所有可达路径

题目描述

​ 给定一个有 n 个节点的有向无环图,节点编号从 1 到 n。请编写一个函数,找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入描述

​ 第一行包含两个整数 N,M,表示图中拥有 N 个节点,M 条边

​ 后续 M 行,每行包含两个整数 s 和 t,表示图中的 s 节点与 t 节点中有一条路径

输出描述

输出所有的可达路径,路径中所有节点之间空格隔开,每条路径独占一行,存在多条路径,路径输出的顺序可任意。如果不存在任何一条路径,则输出 -1。

注意输出的序列中,最后一个节点后面没有空格! 例如正确的答案是 1 3 5,而不是 1 3 5 , 5后面没有空格!

输入示例
5 5
1 3
3 5
1 2
2 4
4 5
输出示例
1 3 5
1 2 4 5
提示信息

img

用例解释:

​ 有五个节点,其中的从 1 到达 5 的路径有两个,分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

​ 因为拥有多条路径,所以输出结果为:

​ 1 3 5 1 2 4 5或1 2 4 5 1 3 5 都算正确。

数据范围:

  • ​ 图中不存在自环
  • ​ 图中不存在平行边
  • ​ 1 <= N <= 100
  • ​ 1 <= M <= 500

邻接矩阵法

def dfs(matrices,path,res,node,n):if node==n:res.append(path[:])returnfor i in range(1,n+1):  # 每层有n个叶子节点if matrices[node][i]==1:path.append(i)dfs(matrices,path,res,i,n)path.pop()  # 回溯def main():n,m=map(int,input().split())# 创建邻接矩阵matrices=[[0 for _ in range(n+1)] for _ in range(n+1)]for _ in range(m):start,end=map(int,input().split())matrices[start][end]=1res=[]dfs(matrices,[1],res,1,n)if len(res)==0:print(-1)else:for path in res:print(' '.join(map(str,path)))if __name__=='__main__':main()

运行结果

在这里插入图片描述


邻接表法

from collections import defaultdict
def dfs(graph,res,path,node,n):if node==n:res.append(path[:])return for i in graph[node]:  # 遍历每层叶子节点path.append(i)dfs(graph,res,path,i,n)path.pop()  # 回溯def main():n,m=map(int,input().split())# 创建邻接表graph=defaultdict(list)for _ in range(m):start,end=map(int,input().split())graph[start].append(end)res=[]dfs(graph,res,[1],1,n)if not res:print(-1)else:for path in res:print(' '.join(map(str,path)))if __name__=='__main__':main()

运行结果

在这里插入图片描述



797. 所有可能的路径

给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序

graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。

示例 1:

img

输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2:

img

输入:graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出:[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

class Solution:def __init__(self):self.path=[]self.res=[]def dfs(self,graph,node,n):if node==n-1:self.res.append(self.path[:])return for node in graph[node]:self.path.append(node)self.dfs(graph,node,n)self.path.pop()def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:self.path.append(0)self.dfs(graph, 0, len(graph))return self.res 

运行结果

在这里插入图片描述

相关文章:

Day 55 卡玛笔记

这是基于代码随想录的每日打卡 所有可达路径 题目描述 ​ 给定一个有 n 个节点的有向无环图&#xff0c;节点编号从 1 到 n。请编写一个函数&#xff0c;找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。 输入描述 ​ 第一行包含两个整数…...

python量化交易——金融数据管理最佳实践——使用qteasy管理本地数据源

文章目录 统一定义的金融历史数据表最重要的数据表数据表的定义交易日历表的定义&#xff1a;交易日历表: trade_calendar qteasy是一个功能全面且易用的量化交易策略框架&#xff0c; Github地址在这里。使用它&#xff0c;能轻松地获取历史数据&#xff0c;创建交易策略并完…...

AVM 环视拼接 鱼眼相机

https://zhuanlan.zhihu.com/p/651306620 AVM 环视拼接方法介绍 从内外参推导IPM变换方程及代码实现&#xff08;生成AVM环视拼接图&#xff09;_avm拼接-CSDN博客 经典文献阅读之--Extrinsic Self-calibration of the Surround-view System: A Weakly... (环视系统的外参自…...

计算机基础面试(数据库)

1. 事务的ACID特性&#xff1f;如何通过日志保证原子性和持久性&#xff1f; 专业解答&#xff1a; ACID&#xff1a;原子性&#xff08;Atomicity&#xff09;、一致性&#xff08;Consistency&#xff09;、隔离性&#xff08;Isolation&#xff09;、持久性&#xff08;Dura…...

Self-Pro: A Self-Prompt and Tuning Framework for Graph Neural Networks

Self-Pro: A Self-Prompt and Tuning Framework for Graph Neural Networks ​#paper/GFM/GNN-BASED#​ #paper/⭐⭐⭐#​ 注意&#xff1a;这篇文章是每个图一个GCN模型&#xff0c;而不是所有图一个GCN 模型 算是最早的涉及异配图的prompt了 贡献和动机&#xff1a; 非对…...

Spring Boot 与 MyBatis 版本兼容性

初接触Spring Boot&#xff0c;本次使用Spring Boot版本为3.4.3&#xff0c;mybatis的起步依赖版本为3.0.0&#xff0c;在启动时报错&#xff0c;报错代码如下 org.springframework.beans.factory.BeanDefinitionStoreException: Invalid bean definition with name userMapper…...

WPF 如何使文本显示控件支持显示内容滚动显示

WPF中如何使文本显示控件支持显示内容滚动显示 在WPF中&#xff0c;TextBlock 控件本身并不直接支持滚动功能&#xff0c;因为它的设计初衷是用于静态文本展示。但是&#xff0c;你可以通过一些技巧和自定义控件来实现 TextBlock 的滚动效果。以下是几种常见的方法&#xff1a;…...

1208. 尽可能使字符串相等

目录 一、题目二、思路2.1 解题思路2.2 代码尝试2.3 疑难问题 三、解法四、收获4.1 心得4.2 举一反三 一、题目 二、思路 2.1 解题思路 2.2 代码尝试 class Solution { public:int equalSubstring(string s, string t, int maxCost) {int curcost0;//统计当前开销int left0;…...

Linux系统管理操作

一、关闭防火墙 默认端口号是22&#xff0c;其他端口用不了&#xff0c;这时候就引出关闭防火墙 1.1、systemctl 1.1.1、基本语法 systemctl start | stop | restart | status 服务名 //启动、关闭、重启、查看状态 1.1.2、查看服务的方法 查看/usr/lib/systemd/syst…...

【STM32H743IIT6】将外部SDRAM作为内部SRAM使用的方法及需要解决的问题

前言 STM32H743的片上随机存取存储器&#xff08;RAM&#xff09;容量最大约为1KB。对于简单项目而言&#xff0c;这一容量尚可满足需求。但在处理更为复杂的应用程序时&#xff0c;尤其是在随机存取存储器方面&#xff0c;“空间不足”的问题就会不可避免地出现。此时&#x…...

AMD RDNA3 GPU架构解析

本文会通过把AMD的RDNA3架构为例比喻为**“施工公司”**工作模式&#xff0c;深入理解GPU如何高效处理顶点着色、像素计算等任务。 一、施工公司的组织架构 1. 施工公司&#xff08;WGP&#xff09;与施工队&#xff08;CU&#xff09; WGP&#xff08;Work Group Processor&…...

博客系统--测试报告

博客系统--测试报告 项目背景项目功能功能测试①登录功能测试②发布博客功能测试③删除文章功能测试④功能测试总结&#xff1a; 自动化测试自动化脚本执行界面&#xff1a; 性能测试 本博文主要针对个人实现的项目《博客系统》去进行功能测试、自动化测试、性能测试&#xff0…...

打造个人知识库(Page Assist版)- 私人专属AI-本地化部署deepseek

上篇介绍了实现浏览器交互Ai Web Ui - chrome浏览器插件-Page Assist&#xff0c;安装即可使用&#xff0c;实现最简单的本地化部署AI使用。 实现浏览器交互Ai Web Ui-本地化部署的deepseek Ollama Page Assist 本编介绍使用 Page Assist 构建个人知识库&#xff0c;利用个…...

7zip安装与使用

在 Linux 上安装 7zip&#xff08;7z&#xff09; 取决于你的操作系统发行版。以下是不同系统的安装方法&#xff1a; &#x1f4cc; 1. Ubuntu / Debian 直接使用 p7zip&#xff1a; sudo apt update sudo apt install -y p7zip-full p7zip-rarp7zip-full → 支持 .7z 压缩和…...

蓝桥杯第15届真题解析

由硬件框图可以知道我们要配置LED 和按键、lcd&#xff0c;解决lcd引脚冲突 LED 先配置LED的八个引脚为GPIO_OutPut&#xff0c;锁存器PD2也是&#xff0c;然后都设置为起始高电平&#xff0c;生成代码时还要去解决引脚冲突问题 按键 按键配置&#xff0c;由原理图按键所对引…...

springboot gradle 多项目创建

1.背景2.创建父项目3.配置gradlew4.创建子项目 1.背景 1.用IDE创建一个父项目&#xff08;school_project&#xff09;&#xff0c;两个子项目&#xff08;student_project&#xff0c;teacher_project)。子项目是两个springboot工程 2.使用gradle kotlin进行管理&#xff0c;…...

Protocol Buffers在MCU上的nanopb介绍及使用详解

在嵌入式系统和资源受限的环境中&#xff0c;传统的Protocol Buffers 可能显得过于庞大。因此&#xff0c;nanopb 应运而生&#xff0c;它是一个轻量级的 Protocol Buffers 生成器&#xff0c;专为嵌入式系统设计c语言设计。本文将介绍如何安装和使用 nanopb&#xff0c;以及通…...

leetcode日记(74)扰乱字符串

很有难度的一题&#xff0c;一开始真的绕了很多思维上的弯路。 最开始的想法是递归&#xff0c;看到题目的时候想到动态规划但是完全没有思路应该怎么用&#xff0c;结果确实是递归动态规划。 最开始的想法是构建树&#xff0c;每一层包含这一步划分的方法&#xff08;实际会…...

Blazor-根级别级联值

根级别级联值注册 using Microsoft.AspNetCore.Components.Web; using Microsoft.AspNetCore.Components.WebAssembly.Hosting;namespace BlazorApp1 {public class Program{public static async Task Main(string[] args){var builder WebAssemblyHostBuilder.CreateDefault…...

懒加载能够解决Spring循环依赖吗

懒加载本身并不能直接解决 Spring 循环依赖问题&#xff0c;但它可以在一定程度上缓解或绕过循环依赖带来的问题&#xff0c;下面详细分析&#xff1a; 1. 什么是 Spring 循环依赖 循环依赖指的是两个或多个 Bean 之间相互依赖&#xff0c;形成一个闭环。例如&#xff0c;Bea…...

Matlab中使用GUIDE工具开发图形用户界面(GUI)

文章目录 1. 初识GUIDE工具1.1 .m 和 .fig的区别和联系1.2 GUIDE工具的详细介绍1.3 GUI控件的属性1.4 自动生成的 .m 文件1.5 回调函数 2. GUI中常见的函数2.1 get 和 set 函数2.2 handles.Tag2.3 OpeningFcn 和 OutputFcn2.4 Callback2.5 CreateFcn 和 DeleteFcn2.6 ButtonDow…...

[通俗易懂C++]:引用返回和地址返回

在之前的文章中已经提到过,当使用按值传递时会创建参数的一个副本到函数中。对于基本类型(复制成本较低),这是可以的。但对于类类型(如 std::string ),复制通常成本较高。我们可以通过使用(const)引用传递(或按地址传递)来避免进行昂贵的复制。 这篇文章主要介绍一些…...

基于 ‌MySQL 数据库‌对三级视图(用户视图、DBA视图、内部视图)的详细解释

基于 ‌MySQL 数据库‌对三级视图&#xff08;用户视图、DBA视图、内部视图&#xff09;的详细解释&#xff0c;结合理论与实际操作说明&#xff1a; 一、三级视图核心概念 数据库的三级视图是 ANSI/SPARC 体系结构的核心思想&#xff0c;MySQL 的实现逻辑如下&#xff1a; …...

LLM - Attention Is All You Need 的理解

一:概述 当前主流的序列转换(sequence transduction)模型主要基于复杂的循环神经网络(Recurrent Neural Networks, RNNs)或卷积神经网络(Convolutional Neural Networks, CNNs),这些模型通常包含编码器(encoder)和解码器(decoder)。 性能最优的模型通常通过“ 注意…...

究竟什么是AI提示词?深入解析与实战应用

随着人工智能技术的飞速发展&#xff0c;AI提示词&#xff08;AI Prompt&#xff09;逐渐成为自然语言处理&#xff08;NLP&#xff09;领域的热门话题。无论是GPT-3、ChatGPT还是其他大型语言模型&#xff0c;提示词都扮演着至关重要的角色。那么&#xff0c;究竟什么是AI提示…...

deep-research开源框架 Agentic Reasoning

Agentic-Reasoning是由牛津大学团队开源的推理框架. 该框架在GPQA博士级科学题库上准确率提升35%&#xff0c;生物学问题得分从62%跃升至79%&#xff0c;显著优于DeepSeek-R1等闭源模型。 特色&#xff1a;Agentic-Reasoning在定义和实现code agent上做的非常出色。可以借鉴。…...

解锁智能变革密码:浙江大学2025年DeepSeek行业应用案例集深度解析

引言&#xff1a;AI技术驱动的时代浪潮 2025年&#xff0c;人工智能技术已从实验室走向千行百业&#xff0c;成为推动社会经济发展的核心引擎。在这一背景下&#xff0c;浙江大学联合DeepSeek团队推出的《2025年DeepSeek行业应用案例集》&#xff08;以下简称“案例集”&#…...

C# Unity 唐老狮 No.5 模拟面试题

本文章不作任何商业用途 仅作学习与交流 安利唐老狮与其他老师合作的网站,内有大量免费资源和优质付费资源,我入门就是看唐老师的课程 打好坚实的基础非常非常重要: 全部 - 游习堂 - 唐老狮创立的游戏开发在线学习平台 - Powered By EduSoho 如果你发现了文章内特殊的字体格式,…...

《2025软件测试工程师面试》功能测试篇

什么是功能测试? 功能测试是通过验证产品功能是否满足用户需求的过程,主要关注软件的功能是否符合需求规格说明,包括软件的各种功能、特性、性能、安全性和易用性等。 功能测试的流程包括哪些步骤? 需求分析:明确软件需求,确定测试范围。测试计划:制定详细的测试计划,…...

DeepSeek如何快速开发PDF转Word软件

一、引言 如今&#xff0c;在线工具的普及让PDF转Word成为了一个常见需求&#xff0c;常见的PDF转Word工具有收费的WPS&#xff0c;免费的有PDFGear&#xff0c;以及在线工具SmallPDF、iLovePDF、24PDF等。然而&#xff0c;大多数免费在线转换工具存在严重隐私风险——文件需上…...

ROS环境搭建

ROS首次搭建环境 注&#xff1a;以下内容都是在已经安装好ros的情况下如何搭建workplace 一、创建工作空间二、创建ROS包三、注意 注&#xff1a;以下内容都是在已经安装好ros的情况下如何搭建workplace 如果没有安装好&#xff0c;建议鱼香ros一步到位:鱼香ROS 我也是装了好久…...

深入探索DeepSeek开源之旅:开源Week全程解析

摘要 在农历新年刚刚结束之际&#xff0c;DeepSeek以卓越的开源精神&#xff0c;连续六天举办了开源Week活动。这一系列活动不仅展示了DeepSeek在技术领域的活跃度和影响力&#xff0c;还彰显了其对开源社区的贡献。通过这次活动&#xff0c;DeepSeek吸引了众多开发者和技术爱好…...

Redis是什么?如何使用Redis进行缓存操作?

Redis&#xff08;Remote Dictionary Server&#xff09;是一款高性能的内存键值存储系统&#xff0c;广泛用于缓存、消息队列、会话存储和实时数据处理等场景。它基于内存存储&#xff0c;支持多种数据结构&#xff0c;如字符串、列表、集合、有序集合和哈希表等&#xff0c;具…...

Unity学习笔记之——ugui的性能优化

在Unity中UI优化的核心问题就是重绘和批处理之间的平衡 一、Canvas优化要点 1.优化原因&#xff1a; &#xff08;1&#xff09;Unity为了性能优化&#xff0c;会合并Canvas下的所有元素&#xff1b; &#xff08;2&#xff09;如果把所有面板放到一个Canvas下&#xff0c;会…...

【三.大模型实战应用篇】【2.智能学员辅导系统:与大模型的深度交互】

早上七点半,初三学生小林打开数学辅导APP,发现AI老师准确指出了他昨晚作业中三次跳步计算的坏习惯——这比他亲妈观察得还细致。这背后是一场发生在代码深处的"脑力风暴",让我们潜入智能辅导系统与大模型深度交互的"暗室",看看那些让教育产生化学反应的…...

【vue-echarts】——04.配置项---legend

文章目录 一、配置项-legend图例二、显示结果一、配置项-legend图例 图例组件展现了不同系列的标记,颜色和名字。可以通过点击图例控制哪些系列不显示。 代码如下 Demo4View.vue <template><div class="about">...

面试题02.02.返回倒数第k个节点

实现一种算法&#xff0c;找出单向链表中倒数第 k 个节点。返回该节点的值。 注意&#xff1a;本题相对原题稍作改动 示例&#xff1a; 输入&#xff1a; 1->2->3->4->5 和 k 2 输出&#xff1a; 4 说明&#xff1a; 给定的 k 保证是有效的。 题解&#xff…...

剑指 Offer II 041. 滑动窗口的平均值

comments: true edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20041.%20%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E7%9A%84%E5%B9%B3%E5%9D%87%E5%80%BC/README.md 剑指 Offer II 041. 滑动窗口的平均值 题目描述 给定一个整数…...

OCR PDF 文件是什么?它包含什么内容?

有些 PDF 文件是通过扫描纸质书页生成的&#xff0c;这类文件有其独特的特点。有时&#xff0c;原始书籍是唯一可用的版本&#xff0c;因此只能通过扫描的方式获取内容。 如何识别 OCR PDF 文件&#xff1f; 你通常可以从外观上辨别 OCR PDF 文件——页面上的文本看起来像“锯…...

什么是最终一致性,它对后端系统的意义是什么

最终一致性(Eventual Consistency)是分布式系统中的一种一致性模型。与传统的强一致性模型不同,最终一致性并不要求系统在任何时刻都保持一致,而是保证在足够的时间后,所有节点的数据最终会达到一致的状态。换句话说,系统允许短时间内出现数据的不一致性,但最终会通过某…...

CSS3中布局方式说明

CSS3 提供了多种灵活的布局方式&#xff0c;适用于不同的场景和需求。以下是主要的布局方式及其特点&#xff1a; 1. Flexbox 布局&#xff08;弹性盒子&#xff09; 用途&#xff1a;一维布局&#xff08;水平或垂直方向排列元素&#xff09;。特点&#xff1a; 通过 display…...

【开源-常用开源c/c++日志管理模块对比】

[TOC]&#xff08;开源-常用开源c/c日志管理模块对比&#xff09; 项目名称语言优点缺点适用场景开源代码链接spdlogC高性能&#xff0c;支持异步日志&#xff1b;丰富的格式化功能&#xff1b;跨平台&#xff1b;易于集成。依赖C11或更高版本&#xff1b;不适合嵌入式系统。高…...

基于log4j的自定义traceid实现

思路就是spring 做切面拦截请求&#xff0c;切面入口时生成traceId&#xff0c;然后放到MDC里面&#xff08;就是threadLocal&#xff0c;MDC是log框架提供的工具类&#xff0c;能方便在配置文件里面引用插入的值&#xff09;。 切面结束时traceId。 import com.sing.monitor…...

如何在网页上显示3D CAD PMI

在现代制造业中&#xff0c;3D CAD模型已成为产品设计和制造的核心。为了更有效地传达设计意图和制造信息&#xff0c;产品和制造信息&#xff08;PMI&#xff09;被嵌入到3D模型中。然而&#xff0c;如何在网页上清晰、准确地显示这些3D CAD PMI&#xff0c;成为了一个重要的技…...

LLMR: Real-time Prompting of Interactive Worldsusing Large Language Models

LLMR-使用大型语言模型的交互式世界实时建模 ABSTRACT 我们提出了混合现实的大语言模型&#xff08;LLMR&#xff09;&#xff0c;一个使用LLM实时创建和修改交互式混合现实体验的框架。LLMR利用新颖的策略来解决理想训练数据稀缺的困难情况&#xff0c;或者设计目标需要综合内…...

使用 OpenLIT 对 LLM 应用进行可观测

大规模语言模型&#xff08;LLM&#xff09;的可观测性 随着大规模语言模型&#xff08;LLM&#xff09;在各个领域的广泛应用&#xff0c;确保这些模型的稳定性和性能变得至关重要。为了实现这一目标&#xff0c;可观测性&#xff08;Observability&#xff09;成为了一个关键…...

C与C++的区别

C 深度剖析&#xff1a;对比 C 语言的显著差异 在编程的浩瀚宇宙中&#xff0c;C 和 C 堪称两颗耀眼的巨星&#xff0c;各自绽放出独一无二的光彩。C 语言作为经典的结构化编程语言&#xff0c;多年来在系统开发、嵌入式编程等领域始终占据着举足轻重的地位。而 C 作为 C 语言…...

【极客时间】浏览器工作原理与实践-2 宏观视角下的浏览器 (6讲) - 2.6 渲染流程(下):HTML、CSS和JavaScript,是如何变成页面的?

https://time.geekbang.org/column/article/118826 2.6 渲染流程&#xff08;下&#xff09;&#xff1a;HTML、CSS和JavaScript&#xff0c;是如何变成页面的&#xff1f; 2.5介绍了渲染流水线中的 DOM 生成、样式计算和布局三个阶段&#xff0c;2.6讲解渲染流水线后面的阶段…...

开放鸿蒙认证,OpenHarmony兼容性认证介绍

Ⅰ、OpenHarmony开放鸿蒙兼容性测试认证&#xff1a;使用官方测试套件&#xff0c;对照PCS自检表中的必测项&#xff0c;在本地搭建的环境中对伙伴设备进行预测&#xff0c;直至取得合格的兼容性测试报告。 注&#xff1a;2025年01月01日起&#xff0c;不支持新产品基于老分支…...

磁盘空间不足|如何安全清理以释放磁盘空间(开源+节流)

背景&#xff1a; 最近往数据库里存的东西有点多&#xff0c;磁盘不够用 查看磁盘使用情况 df -h /dev/sda5&#xff08;根目录 /&#xff09; 已使用 92% 咱们来开源节流 目录 背景&#xff1a; 一、开源 二、节流 1.查找 大于 500MB 的文件&#xff1a; 1. Snap 缓存…...