LeetCode题练习与总结:克隆图--133

2024-06-21 19:52

本文主要是介绍LeetCode题练习与总结:克隆图--133,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目描述

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 valint) 和其邻居的列表(list[Node])。

class Node {public int val;public List<Node> neighbors;
}

测试用例格式:

简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1:

输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。

示例 2:

输入:adjList = [[]]
输出:[[]]
解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。

示例 3:

输入:adjList = []
输出:[]
解释:这个图是空的,它不含任何节点。

提示:

  • 这张图中的节点数在 [0, 100] 之间。
  • 1 <= Node.val <= 100
  • 每个节点值 Node.val 都是唯一的,
  • 图中没有重复的边,也没有自环。
  • 图是连通图,你可以从给定节点访问到所有节点。

二、解题思路

这个问题是图遍历和复制的问题。可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历图。遍历过程中,需要记录已经访问过的节点,以避免重复访问。同时,在复制每个节点时,需要复制它的邻居列表。

具体步骤如下:

1. 检查输入节点是否为空。如果为空,返回null。

2. 创建一个HashMap来存储原始节点和对应的克隆节点,用于避免重复克隆。

3. 使用DFS或BFS遍历图,对于每个访问的节点:

  • 如果该节点已经在HashMap中,说明已经克隆过,直接从HashMap中获取克隆节点。
  • 如果该节点不在HashMap中,创建一个新的克隆节点,并将原始节点和克隆节点的映射关系存入HashMap。
  • 遍历原始节点的邻居列表,对于每个邻居节点,递归地进行克隆操作,并将克隆后的邻居节点添加到克隆节点的邻居列表中。

4. 返回HashMap中存储的输入节点的克隆节点。

三、具体代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;class Solution {public Node cloneGraph(Node node) {if (node == null) {return null;}HashMap<Node, Node> visited = new HashMap<>();return dfs(node, visited);}private Node dfs(Node node, HashMap<Node, Node> visited) {if (visited.containsKey(node)) {return visited.get(node);}Node cloned = new Node(node.val, new ArrayList<>());visited.put(node, cloned);for (Node neighbor : node.neighbors) {cloned.neighbors.add(dfs(neighbor, visited));}return cloned;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 对于每个节点,我们只访问一次,因为一旦一个节点被克隆并放入visited哈希表中,我们就不会再次克隆它。
  • 对于每个节点,我们需要遍历其所有的邻居节点,并进行克隆。
  • 假设图中一共有N个节点和E条边,那么每个节点都会被访问一次,每条边也会被访问一次(因为每条边都会使我们在邻居节点之间进行一次转移)。
  • 因此,时间复杂度为O(N + E),其中N是节点数,E是边数。
2. 空间复杂度
  • 我们需要一个visited哈希表来存储已经访问过的节点和它们的克隆节点,这个哈希表的大小与节点数N成正比。
  • 递归调用栈的最大深度取决于图的最大深度,也就是图中的最长路径。在最坏的情况下,图可能是一个链状结构,递归调用栈的深度为N
  • 因此,空间复杂度也是O(N),主要取决于visited哈希表和递归调用栈的空间消耗。

综上所述,该算法的时间复杂度为O(N + E),空间复杂度为O(N)

五、总结知识点

  1. 图的深度优先搜索(DFS):这是一种用于遍历或搜索树或图的算法。在这个算法中,我们从一个节点开始,探索尽可能深的分支,直到目标节点,然后回溯到之前的分支点,探索新的分支。

  2. 递归dfs函数是递归的,它调用自身来处理图的每个节点和它们的邻居。

  3. 哈希表(HashMap)visited是一个哈希表,用于存储已经访问过的节点和它们的克隆。它提供了快速的查找和插入操作,这对于避免重复克隆节点至关重要。

  4. 引用类型和值类型:在Java中,Node是一个引用类型,这意味着visited哈希表中存储的是节点的引用,而不是节点的副本。

  5. 链表(ArrayList)ArrayList用于存储节点的邻居列表。它是一个可调整大小的数组实现,提供了对列表的快速随机访问。

  6. 对象的创建和初始化new Node(node.val, new ArrayList<>())创建了一个新的Node对象,并使用节点值和空的邻居列表进行了初始化。

  7. 迭代for循环用于迭代节点的邻居列表,对每个邻居节点调用dfs函数。

  8. 函数返回值dfs函数返回克隆后的节点,这允许递归调用将克隆的邻居节点添加到当前节点的邻居列表中。

  9. 基础数据结构操作:代码中涉及了哈希表和列表的基本操作,如添加元素(putadd)和检查元素是否存在(containsKey)。

  10. 边界条件处理:代码首先检查输入节点是否为空,这是处理图问题时常见的边界条件。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

这篇关于LeetCode题练习与总结:克隆图--133的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1082177

相关文章

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用

Nginx Location映射规则总结归纳与最佳实践

《NginxLocation映射规则总结归纳与最佳实践》Nginx的location指令是配置请求路由的核心机制,其匹配规则直接影响请求的处理流程,下面给大家介绍NginxLocation映射规则... 目录一、Location匹配规则与优先级1. 匹配模式2. 优先级顺序3. 匹配示例二、Proxy_pa

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li

Linux区分SSD和机械硬盘的方法总结

《Linux区分SSD和机械硬盘的方法总结》在Linux系统管理中,了解存储设备的类型和特性是至关重要的,不同的存储介质(如固态硬盘SSD和机械硬盘HDD)在性能、可靠性和适用场景上有着显著差异,本文... 目录一、lsblk 命令简介基本用法二、识别磁盘类型的关键参数:ROTA查询 ROTA 参数ROTA

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解