首页 > 其他分享 >133.克隆图

133.克隆图

时间:2024-08-28 10:55:13浏览次数:15  
标签:Node neighbors 结点 克隆 val map 133 节点

1.题目描述

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

图中的每个节点都包含它的值 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 都是唯一的,
  • 图中没有重复的边,也没有自环。
  • 图是连通图,你可以从给定节点访问到所有节点。

2.解题思路

因为要把结点和边全都进行拷贝,因此不能简单的复制,要通过广度优先遍历源图每一个点和边,在遍历的过程中,给新图上的结点和边也赋上相同的值,但如何将新图中的结点和源图中的结点对应上从而做相同的赋值操作呢,例如遍历到原图上的结点1,他有两个邻居2,3,我们就需要在新图上的结点,给它的neighbors域赋上2,3这两个结点的值。这就需要使用一个hashMap对原图和新图中对应结点做映射,以原图中Node作为key,新图中的Node作为value,只要map中存在当前遍历结点,那么就直接取,不存在就复制一个节点,并把新老结点的映射Put到map中,以此进行图的深拷贝

3.代码实现

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        Node res = null;
        boolean[] visited = new boolean[101];
        //源结点 和 拷贝结点的映射
        Map<Node,Node> map = new HashMap<>();
        //广度优先遍历图,在遍历的过程中进行克隆
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (visited[cur.val]) {
                continue;
            }
            visited[cur.val] = true;
            Node copyCur = null;
            if (!map.containsKey(cur)) {
                copyCur = new Node(cur.val);
                res = copyCur;
                map.put(cur,copyCur);
            } else {
                copyCur = map.get(cur);
            }
            for (Node neigh : cur.neighbors) {
                if (!map.containsKey(neigh)) {
                    Node copyNeigh = new Node(neigh.val);
                    map.put(neigh,copyNeigh);
                    copyCur.neighbors.add(copyNeigh); 
                } else {
                    copyCur.neighbors.add(map.get(neigh));
                }
                if (!visited[neigh.val]) {
                    queue.offer(neigh);
                }
            }
        }
        return res;
    }
}

标签:Node,neighbors,结点,克隆,val,map,133,节点
From: https://blog.csdn.net/cqjnovo/article/details/141635067

相关文章

  • mysql8.0.39采用克隆方式快速搭建主从同步
    mysql8.0.39采用克隆方式快速搭建主从同步备注:基于物理文件拷贝,数据量越大,越能体现出这种优势。8.0.17以上都可以使用 一、环境192.168.0.101主库192.168.0.102从库Serverversion:8.0.39 二、查看是否已经安装克隆插件#如果没有同步账号,可以新建一个dropus......
  • 结构化克隆算法是啥?
    结构化克隆算法(StructuredCloneAlgorithm)是一种用于在Web浏览器中复制复杂数据类型的方法,主要用于postMessageAPI。它允许从一个环境(如一个窗口或Worker)向另一个环境发送消息,而这些消息可以是复杂的JavaScript对象。基本原理结构化克隆算法的基本思想是在发送方创建一......
  • CodeForces - 1336A Linova and Kingdom
    CodeForces-1336A就差一点点,很可惜,少发现个很显而易见的结论就是一个点的价值,实际上就是(这个点的深度-之后的点的数目)就是\(depth_i-size_i\)然后只要用dfs维护就好了然后把一个点的价值用STL优先队列放在一起,贪心完成。但是可能也算不上什么贪心,因为是很朴素的东西......
  • 声音克隆GPT-SoVITS 2.0软件和详细的使用教程!
    天命人,请允许我先蹭个热点!  原始声音:播放克隆声音:播放 文章写了一半,被《黑神话悟空》刷屏了。突发奇想,用里面的声音来做个素材试试看。B站捞了一点声音素材,随便剪一剪,训练一把过,没有调优,就直接拿来用了。情绪还差点意思,音色克隆的还不错。......
  • [ABC133D] Rain Flows into Dams 题解
    思路其实就是一道数学题。设每座山的水量为$ans_i$,大坝的水量为$w_i$,则根据题意可以得到以下方程:$$\begin{cases}w_i=\frac{ans_i+ans_{i+1}}{2}&i<n\w_i=\frac{ans_i+ans_1}{2}&i=n\end{cases}$$所以只要求出任意一个$ans$就可以求出剩余的$ans$,这里我选择求$ans_1$的......
  • 模幂运算-要求算法返回幂运算a^b的计算结果与1337取模后的结果
    题目:模幂运算-要求算法返回幂运算a^b的计算结果与1337取模后的结果其中b是一个非常大的数,所以b使用数组形式表示。即无法直接a^b%1337计算此类问题的关键需要分治,拆分成更小规模的计算1)对于a^b,如果b=1234,则a^1234=a^4*(a^123)^10即a^b可以拆分后递归运算2)对于取模运算,(a*b......
  • 《深入剖析原型模式:浅克隆、深克隆与单例模式的碰撞》
    3.原型模式一、引言在Java编程中,原型模式(Prototype)是一种创建对象的方式,通过拷贝原型实例来创建新的对象,为对象的创建提供了一种高效且灵活的途径。本文将详细探讨原型模式的概念、包含的角色、浅克隆与深克隆的实现,以及克隆对单例模式的影响和相应的解决办法。二、原......
  • 魔兽世界:发布网www.SouFu6.cn,新开魔兽世界来袭!133
           魔兽世界:发布网www.SouFu6.cn,新开魔兽世界来袭!152       私服SF有着许多独特的品质,使其与正版游戏区别开来。首先,私服SF通常会提供大量的游戏元素和功能,比如新增的职业、装备、地图等,让玩家能够体验到更丰富的游戏内容。其次,私服SF还通常会......
  • Gitlab怎么使用ssh进行克隆
    系统环境和软件环境查看系统环境#cat/etc/redhat-releaseCentOSStreamrelease9#uname-aLinuxCentOSStream9Git2155.14.0-381.el9.x86_64#1SMPPREEMPT_DYNAMICMonOct3023:56:21UTC2023x86_64x86_64x86_64GNU/Linux软件环境#gitlab-railsconsole......
  • 编写类 MyTools 类,编写一个方法可以打印二维数组的数据。 2) 编写一个方法 copyPerson
    1publicclassMethodExercise02{2publicstaticvoidmain(String[]args){34Personp=newPerson();5p.name="milan";6p.age=100;7//创建tools8MyToolstools=newMyTools();9......