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

图论① dfs | Java | LeetCode 797,Kama 98 邻接表实现(未完成)

797 所有可能路径

https://leetcode.cn/problems/all-paths-from-source-to-target/description/
输入:graph = [[1,2],[3],[3],[]]

题目分析,这里

class Solution {//这个不是二维数组,而是listList<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {path.add(0);dfs(graph, 0);return res;}public void dfs(int graph[][], int x) {if(x == graph.length-1) { //横向的所有节点res.add(new ArrayList<>(path));return;}//列for(int i=0; i<graph[x].length; i++) {path.add(graph[x][i]);dfs(graph, graph[x][i]);path.remove(path.size()-1);}}
}

Kama 98

题目链接 https://kamacoder.com/problempage.php?pid=1170

邻接矩阵实现

import java.util.*;public class Main {static List<List<Integer>> res = new ArrayList<List<Integer>>();static List<Integer> path = new ArrayList<Integer>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();int[][]graph = new int[N+1][N+1];//这个for循环for(int i=0; i<M; i++) {int s = sc.nextInt();int t = sc.nextInt();graph[s][t] = 1;}path.add(1);dfs(graph, 1);if (res.isEmpty()) System.out.println(-1);for (List<Integer> pa : res) {for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));}}public static void dfs(int[][]graph, int x) {//节点个数int n = graph.length-1;if(x == n) {res.add(new ArrayList<>(path));return;}for(int i=1; i<=n; i++) {if(graph[x][i] == 1) {path.add(i);dfs(graph ,i);path.remove(path.size()-1);}}}
}

出错点

1 与力扣上的题目不一样,首先需要自己设置输入输出

输入的时候,这里for循环是因为告知了有多少条有向边

for(int i=0; i<M; i++) {int s = sc.nextInt();int t = sc.nextInt();graph[s][t] = 1;
}

2 力扣直接给出了图 int graph[][],而且输入样例中 输入:graph = [[1,2],[3],[3],[]],直接表明这个二维数组不是 n×n 的,因此graph.length获得节点的个数,graph[index].length获得以节点index为起点 的边的总数,

  • 力扣797
    在这里插入图片描述

  • 对比:在卡玛98题中,我们在用邻接矩阵创建图的时候,graph是n×n的:int[][]graph = new int[N+1][N+1];。因此在回溯(DFS)的时候,for循环条件不一样,也要多一个if判断
    在这里插入图片描述

3 static的使用,在Kama的ACM模式下 public static void main(String[] args)是入口函数,直接运行了,因此这里定义的函数和变量都需要用 static描述,否则必须要先实例化类Main才能调用函数
在这里插入图片描述

4 Kama的输出:遍历 List<List<Integer>> res

if (res.isEmpty()) System.out.println(-1);for (List<Integer> pa : res) {for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));}

邻接表实现(未完成)

LinkedList

链表是一种常见的数据结构,用于存储和组织数据。它由一系列节点(Node)组成,每个节点包含两个主要部分:数据域(Data)和指针域(Pointer)。

数据域存储节点所需的数据或信息,可以是任意类型的数据,如整数、字符、对象等。指针域则指向链表中的下一个节点,将节点连接起来形成链表结构。

链表中的节点并不一定按照物理上的连续位置存储,而是通过指针域相互连接。这使得链表能够灵活地插入、删除和修改节点,而无需像数组那样进行元素的移动。

链表的优点是可以高效地插入和删除节点,而无需移动其他节点。然而,由于链表中的节点不是连续存储的,访问特定位置的节点需要从头部开始遍历,因此随机访问的效率较低。

在Java中,LinkedList(链表)是Java集合框架提供的一个实现了List接口的类。它是基于双向链表结构实现的,可以用于存储和操作元素的有序集合。

【Java】链表LinkedList

LinkedList和ArrayList是Java集合框架中的两种不同的List实现。

相关文章:

图论① dfs | Java | LeetCode 797,Kama 98 邻接表实现(未完成)

797 所有可能路径 https://leetcode.cn/problems/all-paths-from-source-to-target/description/ 输入&#xff1a;graph [[1,2],[3],[3],[]] 题目分析&#xff0c;这里 class Solution {//这个不是二维数组&#xff0c;而是listList<List<Integer>> res new Ar…...

Mac安装nvm以及配置环境变量

安装nvm brew install nvm安装成功后会出现这样一段话: Add the following to your shell profile e.g. ~/.profile or ~/.zshrc:export NVM_DIR"$HOME/.nvm"[ -s "/opt/homebrew/opt/nvm/nvm.sh" ] && \. "/opt/homebrew/opt/nvm/nvm.sh&q…...

AUTOSAR实战教程-使用DET来发现开发错误

2年之前因为在调试AUTOSAR存储协议栈的时候使用DET并没发现有用的信息,所以就武断下结论--这玩意没有用。活到老学到老吧,bug经历的多了,发现这玩意还挺有用的。说一下这个bug的背景。 在将时间同步报文改道CanTsync之后,由于这个AUTOSAR工具本身的问题以及配置工程师本身的…...

ZeroMQ(二):请求-响应模式,C和C++。

目录 请求响应基础 基本概念 工作流程 典型应用 请求-响应模式的特点 应用实例 优点 缺点 ZEROMQ C语言 2.1 服务器端代码&#xff08;Reply Server&#xff09; 2.2 客户端代码&#xff08;Request Client&#xff09; 3. 编译代码 4. 详细说明 ZEROMQ C 1. …...

【虚拟仿真】Unity3D中实现2DUI显示在3D物体旁边

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址QQ群:398291828大家好,我是佛系工程师☆恬静的小魔龙☆,不定时更新Unity开发技巧,觉得有用记得一键三连哦。 一、前言 这篇文章来实现2DUI显示在3D物体旁边,当我们需要在3D模型旁边显示2DUI的时候,比如人物的对…...

代码随想录 day 29 贪心

第八章 贪心算法 part03 134. 加油站 本题有点难度&#xff0c;不太好想&#xff0c;推荐大家熟悉一下方法二 https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html 135. 分发糖果 本题涉及到一个思想&#xff0c;就是想处理好一边再处理另一边&#xff0c;不…...

开源:LLMCompiler高性能工具调用框架

开源&#xff1a;LLMCompiler高性能工具调用框架 LLMCompilerLLMCompiler 框架图任务提取单元使用方式参考链接 LLMCompiler LLMCompiler 是一种 Agent 架构&#xff0c;旨在通过在DAG中快速执行任务来加快 Agent 任务的执行速度。它还通过减少对 LLM 的调用次数来节省 Tokens …...

【学习方法】高效学习因素 ① ( 开始学习 | 高效学习因素五大因素 | 高效学习公式 - 学习效果 = 时间 x 注意力 x 精力 x 目标 x 策略 )

文章目录 一、高效学习因素1、开始学习2、高效学习因素五大因素3、高效学习公式 - 学习效果 时间 x 注意力 x 精力 x 目标 x 策略 一、高效学习因素 1、开始学习 对于 学习差 , 调皮捣蛋 的学生 , 不要把 学习成绩差 的 原因 归因为 不爱学习 / 没有学习方法 , 可能是 还没有 …...

LeetCode Medium|【146. LRU 缓存】

力扣题目链接 题意&#xff1a;本题的题意就是希望我们设计一个满足 LRU 缓存的数据结构&#xff0c;LRU即最近最少使用。 需要我们实现 get 和 put 方法&#xff0c;即从缓存中获取值和设置缓存中值的方法。 还有一个约束条件就是缓存应当有容量限制&#xff0c;如果实现 put …...

(南京观海微电子)——LCD OTP(烧录)介绍

OTP OTP只是一种存储数据的器件&#xff0c;全写:ONETIMEPROGRAM。 OTP目的&#xff1a;提高产品的一致性 客户端的接口不支持和我们自己的产品IC之间通信&#xff0c;即不支持写初始化&#xff0c;所以产品的电学功能以及光学特性需要固化在IC中&#xff0c;所以需要我们来进行…...

[E二叉树] lc572. 另一棵树的子树(dfs+前中序判断+树哈希+树上KMP+好题)

文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接&#xff1a;572. 另一棵树的子树 2. 题目解析 看到这个题目就感觉不简单&#xff0c;因为写了写 dfs 版本的&#xff0c;发现好像不太会… 还是简单粗暴一点&#xff0c;直接搞一个 前序中序&#xff0c;进行判断即可。我…...

C# 设计模式之简单工厂模式

总目录 前言 本文是个人基于C#学习设计模式总结的学习笔记&#xff0c;希望对你有用&#xff01; 1 基本介绍 简单工厂模式 定义&#xff1a;用于创建对象&#xff0c;将对象的创建与使用分离。 简单工厂模式中用于创建实例的方法是静态(static)方法&#xff0c;因而简单工厂…...

mac中dyld[5999]: Library not loaded: libssl.3.dylib解决方法

需要重新安装下openssl3.0版本 brew reinstall openssl3.0 安装后执行还是报错&#xff0c;需要找到openssl的安装路径 /opt/homebrew/Cellar/openssl3.0/3.0.14/lib/ 将libssl.3.dylib和libcrypto.3.dylib拷贝到自己的二进制文件同目录下&#xff0c;再执行二进制文件就可…...

python 容器

文章目录 数据容器特点比较通用序列操作示例代码1. s.index(x[, i[, j]])2. s.count(x)示例代码注意事项代码解释输出结果 数据容器的通用转换1. list()2. tuple()3. str()4. set()5. dict()6. enumerate()7. zip()8. sorted()9. reversed()10. map()11. filter()12. join()示例…...

微信小程序中Component中如何监听属性变化

1.在父组件的.json文件中引入子组件&#xff1a; "usingComponents": {"articleList":"../../components/articleList/articleList",}2.在父组件中给子组件绑定数据 <articleList num"{{number}}"></articleList>3.子组…...

【Python 逆向滑块】(实战五)逆向滑块,并实现用Python+Node.js 生成滑块、识别滑块、验证滑块、发送短信

逆向日期&#xff1a;2024.08.03 使用工具&#xff1a;Python&#xff0c;Node.js 本章知识&#xff1a;滑块距离识别&#xff0c;滑块轨迹生成&#xff0c;验证滑块并获取【validate】参数 文章难度&#xff1a;中等&#xff08;没耐心的请离开&#xff09; 文章全程已做去敏处…...

微服务架构设计的最佳实践

在当今快速变化的软件开发环境中&#xff0c;微服务架构因其灵活性、可扩展性和可维护性而逐渐成为大型分布式系统的首选架构模式。然而&#xff0c;成功实施微服务架构并非易事&#xff0c;它要求开发团队遵循一系列最佳实践来确保系统的可靠性、效率和可管理性。本文将探讨微…...

样式与特效(3)——实现一个测算页面

这次我们使用前端实现一个简单的游戏页面,理论上可以增加很多玩法&#xff0c;&#xff0c;但是这里为了加深前端的样式和JS点击事件&#xff0c;用该案例做练习。 首先需要掌握手机端的自适应&#xff0c;我们是只做手机端玩家页面 。需要允许自适应手机端页面&#xff0c; 用…...

芯片制造过程4光刻机

以下内容均取自哔哩哔哩up主谈三圈 链接: 芯片制造详解04&#xff1a;光刻技术与基本流程&#xff5c;国产之路不容易 1.光刻原理 通过光掩膜、光刻机、光刻胶进行光刻 光掩膜是芯片的蓝图&#xff0c;是一张刻有集成电路板图的玻璃遮光板光刻机就像一台纳米级的打印机&#…...

Nexus3 Repository代理pypi设置与应用

目录 1. 创建Blob库并指定路径 2. 创建pypi阿里镜像源 3. 创建pypi腾讯镜像源 4. 创建一个pypi组管理 5. 配置pip 6. 下载测试 扩展&#xff1a;配置好后无法下载解决思路。 Nexus 存储库中的 Blob 存储是指一种用于存储大量非结构化数据的技术。在 Nexus 存储库的上下文…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...