当前位置: 首页 > 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 存储库的上下文…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...

Copilot for Xcode (iOS的 AI辅助编程)

Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot&#xff0c;它能根据上下文补全代码&#xff0c;快速生成常用…...