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

力扣(LeetCode)133. 克隆图(C++)

dfs+哈希表+图

先深搜建立所有点,加入哈希表。再遍历哈希表,按照拷贝前后的结点,拷贝边。最后返回某一结点,即为所求。

class Solution {
public:
    unordered_map<Node*,Node*> mp;
    Node* cloneGraph(Node* node) {
        if(!node) return node;
        dfs(node);
        for(auto &[s,d]:mp)
            for(auto &e:s->neighbors)
                d->neighbors.push_back(mp[e]);
        return mp[node];
    }
    void dfs(Node *node) {
        mp[node] = new Node(node->val);
        for(auto &v:node->neighbors)
            if(!mp.count(v)) dfs(v);
    }
};
  1. 时间复杂度 : O ( ∑ i = 0 n m i ) O(\sum_{i=0}^{n} m_i) O(i=0nmi) n n n 是点的数量, m m m 是边的数量,遍历所有点的所有边,时间复杂度 O ( ∑ i = 0 n m i ) O(\sum_{i=0}^{n} m_i) O(i=0nmi)
  2. 空间复杂度 : O ( n ) O(n) O(n) , 哈希表存 n n n 个点的空间复杂度 O ( n ) O(n) O(n)

AC

AC

相关文章:

  • Android kotlin实现Viewpager滑动背景透明效果渐变
  • 用Tinyproxy搭建自己的proxy server
  • 简单入门编写html登录界面
  • [网络工程师]-应用层协议-SNMP
  • 【云原生之kubernetes实战】在k8s环境下部署jpress开源网站
  • HTML+CSS+JS网页设计期末课程大作业 DW个人博客网站制作 web前端开发技术 web课程设计 网页规划与设计
  • SpringBoot_整合PageHelper
  • 【数据结构与算法】一套链表 OJ 带你轻松玩转链表
  • C/C++大学课程信息系统
  • 【网络编程】第三章 网络套接字(TCP协议程序+多进程+多线程+线程池)
  • 基于物联网设计的自反馈深紫外杀菌消毒系统(STM32F407)
  • react路由v6版本NavLink的两个小坑及解决
  • CSDN第11期周赛总结
  • 编程语言介绍
  • 【火灾检测】森林火灾检测系统(带面板)【含GUI Matlab源码 1921期】
  • [iOS]Core Data浅析一 -- 启用Core Data
  • [译] 怎样写一个基础的编译器
  • 【面试系列】之二:关于js原型
  • css布局,左右固定中间自适应实现
  • GraphQL学习过程应该是这样的
  • Java 多线程编程之:notify 和 wait 用法
  • JS学习笔记——闭包
  • linux安装openssl、swoole等扩展的具体步骤
  • Magento 1.x 中文订单打印乱码
  • 多线程 start 和 run 方法到底有什么区别?
  • 今年的LC3大会没了?
  • 入门级的git使用指北
  • 网络应用优化——时延与带宽
  • 移动互联网+智能运营体系搭建=你家有金矿啊!
  • 如何在 Intellij IDEA 更高效地将应用部署到容器服务 Kubernetes ...
  • ​VRRP 虚拟路由冗余协议(华为)
  • ​虚拟化系列介绍(十)
  • #ifdef 的技巧用法
  • (1)Map集合 (2)异常机制 (3)File类 (4)I/O流
  • (html转换)StringEscapeUtils类的转义与反转义方法
  • (附源码)springboot课程在线考试系统 毕业设计 655127
  • (附源码)ssm考生评分系统 毕业设计 071114
  • (三) prometheus + grafana + alertmanager 配置Redis监控
  • (十八)SpringBoot之发送QQ邮件
  • .java 9 找不到符号_java找不到符号
  • .NET DataGridView数据绑定说明
  • .NET 服务 ServiceController
  • .NET(C#) Internals: as a developer, .net framework in my eyes
  • .NET/MSBuild 中的发布路径在哪里呢?如何在扩展编译的时候修改发布路径中的文件呢?
  • .net的socket示例
  • .NET业务框架的构建
  • /usr/bin/env: node: No such file or directory
  • [ 环境搭建篇 ] 安装 java 环境并配置环境变量(附 JDK1.8 安装包)
  • []串口通信 零星笔记
  • [《百万宝贝》观后]To be or not to be?
  • [20140403]查询是否产生日志
  • [20150904]exp slow.txt
  • [4.9福建四校联考]
  • [Android]使用Android打包Unity工程
  • [Dxperience.8.*]报表预览控件PrintControl设置
  • C语言字符数组和字符串 —— 2022/3/20
  • MySQL创建表
  • javascript的三个函数
  • C语言字符串的输入和输出 —— 2022/3/21
  • 数值转换(十进制转换为二进制)
  • (数据结构)利用 C语言实现三元组 —— 2022/3/22
  • Ecplise中项目出现红色感叹号
  • C语言循环链表实现解决约瑟夫环问题 —— 2022/3/23
  • Git CMD - init: Create an empty Git repository or reinitialize an existing one
  • Mysql学习笔记——MySql导入导出数据库常用方法