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

链表学习之复制含随机指针的链表

链表解题技巧

  • 额外的数据结构(哈希表);
  • 快慢指针;
  • 虚拟头节点;

复制含随机指针的链表

该链表节点的结构如下:

class ListRandomNode {
public:ListRandomNode() : val(0), next(nullptr), random(nullptr) {}ListRandomNode(int v, ListRandomNode *n, ListRandomNode *r) : val(v), next(n), random(r) {}
public:int val;ListRandomNode *next;ListRandomNode *random;
};

要求:时间复杂度O(N),空间复杂度O(1);

方法1:哈希表

时间复杂度O(N),空间复杂度O(N);

具体思路:

  • 遍历链表,复制每个节点并存入map,key为原节点,val为新节点;
  • 再次遍历链表,每个新节点都可以通过源节点和map找到,据此连接next和random;
    • 新节点的next就是,map[源节点]的next;
    • 新节点的random就是,map[源节点]的random;
ListRandomNode* LinkedList::copyListWithRandomByMap(ListRandomNode *head) {if (head == nullptr ) return head;std::unordered_map<ListRandomNode*, ListRandomNode*> ref;// create new nodeListRandomNode *cur = head;while (cur != nullptr) {ListRandomNode *tmp = new ListRandomNode(cur->val, nullptr, nullptr);ref[cur] = tmp;cur = cur->next;}// joint new nodecur = head;while (cur != nullptr) {ref[cur]->next = ref[cur->next];ref[cur]->random = ref[cur->random];cur = cur->next;}return ref[head];
}

方法2:next

时间复杂度O(N),空间复杂度O(1);

将每一个新节点放在原来节点的后面,并连接上下一个节点的方式,这样通过next就能够定位到新节点,通过next的next就能找到原来的下一个节点。

  • 遍历一遍链表,遍历的过程中,为每一个节点创建一个新节点,新节点连接在原来两个节点之间;
  • 再次遍历链表,为random赋值:新节点的random就是,源节点random的next;
  • 再将源节点和新节点分离出来,返回新节点头即可。
ListRandomNode* LinkedList::copyListWithRandom(ListRandomNode *head) {if (head == nullptr) return head;// create new nodeListRandomNode *cur = head;while (cur != nullptr) {ListRandomNode *cur_ = new ListRandomNode(cur->val, nullptr, nullptr);ListRandomNode *tmp = cur->next;cur->next = cur_;cur_->next = tmp;cur = tmp;}// assign random pointerscur = head;while (cur != nullptr) {cur->next->random = cur->random ? cur->random->next : nullptr;cur = cur->next->next;}// splitcur = head;ListRandomNode *new_head = head->next;ListRandomNode *cur_ = head->next;while (cur_->next != nullptr) {cur->next = cur_->next;cur = cur->next;cur_->next = cur->next;cur_ = cur_->next;}cur->next = nullptr;cur_->next = nullptr;return new_head;
}

辅助函数

根据数组生成带随机值的链表:

ListRandomNode* LinkedList::generateListWithRandom(int *arr, int len) {if (arr == nullptr || len < 1) {return nullptr;}std::vector<ListRandomNode*> vec;ListRandomNode *head = new ListRandomNode(arr[0], nullptr, nullptr);ListRandomNode *cur = head;for (int i = 1; i < len; i++) {vec.push_back(cur);cur->next = new ListRandomNode(arr[i], nullptr, nullptr);cur = cur->next;}vec.push_back(cur);for (int i = 0; i < len; i++) {vec[i]->random = vec[rand() % len];}return head;
}

打印随机链表:

void LinkedList::printListWithRandom(ListRandomNode *head) {while (head) {std::cout << head->val << "[" << head->random->val << "]" << (head->next ? "->" : " ") ;head = head->next;}std::cout << std::endl;
}

相关文章:

链表学习之复制含随机指针的链表

链表解题技巧 额外的数据结构&#xff08;哈希表&#xff09;&#xff1b;快慢指针&#xff1b;虚拟头节点&#xff1b; 复制含随机指针的链表 该链表节点的结构如下&#xff1a; class ListRandomNode { public:ListRandomNode() : val(0), next(nullptr), random(nullptr…...

【人脸检测】Yolov5Face:优秀的one-stage人脸检测算法

论文题目&#xff1a;《YOLO5Face: Why Reinventing a Face Detector》 论文地址&#xff1a;https://arxiv.org/pdf/2105.12931.pdf 代码地址&#xff1a;https://github.com/deepcam-cn/yolov5-face 1.简介 近年来&#xff0c;CNN在人脸检测方面已经得到广泛的应用。但是许多…...

【Unity3d】Unity与Android之间通信

在unity开发或者sdk开发经常遇到unity与移动端原生层之间进行通信&#xff0c;这里把它们之间通信做一个整理。 关于Unity与iOS之间通信&#xff0c;参考【Unity3d】Unity与iOS之间通信 Unity(c#)调用Android (一)、编写Java代码 实际上&#xff0c;任何已经存在的Java代码…...

Allegro如何更改DRC尺寸大小操作指导

Allegro如何更改DRC尺寸大小操作指导 在做PCB设计的时候,DRC可以辅助设计,有的时候DRC的尺寸过大会影响视觉,Allegro支持将DRC的尺寸变小或者改大 如下图,DRC尺寸过大 如何改小,具体操作如下 点击Setup选择Design Parameters...

Mongodb WT_PANIC: WiredTiger library panic

文章目录故障现象排查过程1.查看Log2.同步恢复数据故障现象 周五突然收到Mongo实例莫名奇妙挂了告警&#xff0c;一般都是RS复制集架构模式&#xff08;5节点&#xff09;&#xff0c;查看此实例角色为SECONDAR&#xff0c;挂了暂时不影响线上业务&#xff0c;但还是需要尽快修…...

【HTML】HTML 表格总结 ★★★ ( 表格标签 | 行标签 | 单元格标签 | 表格标签属性 | 表头单元格标签 | 表格标题标签 | 合并单元格 )

文章目录一、表格标签组成 ( 表格标签 | 行标签 | 单元格标签 )二、table 表格属性 ( border 属性 | align 属性 | width 属性 | height 属性 )三、表头单元格标签四、表格标题标签五、合并单元格1、合并单元格方式2、合并单元格顺序3、合并单元格流程六、合并单元格示例1、原始…...

linux013之文件和目录的权限管理

用户、组、文件目录的关系&#xff1a; 简介&#xff1a;用户和组关联&#xff0c;组合文件目录关联&#xff0c;这样就实现了用户对文件的权限管理。首先来看一下&#xff0c;一个文件或目录的权限是怎么查看的&#xff0c;ls -l&#xff0c; 如下&#xff0c;这个信息怎么看呢…...

设计模式之状态模式

什么是状态模式 状态模式是指允许一个对象在其内部状态改变时改变他的行为&#xff0c;对象看起来似乎改变了整个类。     状态模式将一个对象在不同状态下的不同行为封装在一个个状态类中&#xff0c;通过设置不同的状态对象可以让环境对象拥有不同的行为&#xff0c;而状…...

XQuery 选择 和 过滤

XML实例文档 我们将在下面的例子中继续使用这个 "books.xml" 文档&#xff08;和上面的章节所使用的 XML 文件相同&#xff09;。 在您的浏览器中查看 "books.xml" 文件。 选择和过滤元素 正如在前面的章节所看到的&#xff0c;我们使用路径表达式或 FL…...

室友打了一把王者的时间,我理清楚了grep,find,管道|,xargs的区别与联系,用的时候不知道为什么要这样用

目录 问题引入 find和grep的基本区别 xargs命令 Linux命令的标准输入 vs 命令行参数 举例总结 问题引入 在自己做项目的过程中&#xff0c;想使用linux命令统计下一个目录下html文件的数量&#xff0c;在思考应该使用grep还是find去配合wc指令统计文件数量&#xff0c;后来…...

python 刷题时常见的函数

collections.OrderedDict 1. move_to_end() move_to_end() 函数可以将指定的键值对移动到最前面或者最后面&#xff0c;即最左边或最右边 。 2. popitem() popitem()可以完成元素的删除操作&#xff0c;有一个可选参数last&#xff08;默认为True&#xff09;&#xff0c;…...

Python之列表推导式和列表排序

Python中的列表推导式&#xff0c;是小编比较喜欢的一种&#xff0c;他能大大减少你的代码量来得到你想要的结果&#xff0c;下面说说列表中常用的几种推导式 列表排序 Python开发中会经常用到排序操作&#xff0c;这里提供两种方式供大家参考&#xff0c;对象的sort()方法和…...

力扣(LeetCode)240. 搜索二维矩阵 II(C++)

题目描述 枚举 枚举整个矩阵&#xff0c;找到等于 target 的元素&#xff0c;则 return true &#xff0c;否则 return false。 class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n matrix.size(), m matrix[0]…...

golang defer

文章目录延迟函数的参数在defer语句出现时就已经确定下来了延迟函数没有入参时&#xff0c;延迟函数体内的变量会受到影响延迟函数 *可以* 修改主函数的 *具名* 返回值延迟函数 *无法* 修改主函数的 *匿名* 返回值defer会把声明的 延迟函数以及 函数的入参放到栈上&#xff0c;…...

【Java】线程的死锁和释放锁

线程死锁是线程同步的时候可能出现的一种问题 文章目录1. 线程的死锁1.1 基本介绍1.2 应用案例2. 释放锁2.1 下面的操作会释放锁2.2 下面的操作不会释放锁1. 线程的死锁 1.1 基本介绍 多个线程都占用了对方的锁资源&#xff0c;但不肯相让&#xff0c;导致了死锁&#xff0c;…...

如何使用断点续传上传大文件

概念 大文件上传的需求介绍 不管怎样简单的需求&#xff0c;在量级达到一定层次时&#xff0c;都会变得异常复杂。 文件上传简单&#xff0c;文件变大就复杂 上传大文件时&#xff0c;以下几个变量会影响我们的用户体验 服务器处理数据的能力请求超时网络波动 上传时间会变长…...

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波 文章目录【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波1. 前言2. 符号说明3. 三种滤波3.1 全通滤波3.2 低通滤波3.2.1 平滑信号分析3.2.2 广义拉普拉斯平滑滤波器3.3 高通滤波4. 总结1. 前言 GCN&…...

python操作mysql数据库详解

使用Python操作MySQL数据库 MySQL是一种关系型数据库管理系统&#xff0c;它可以用来存储和管理大量的数据。之前介绍了大部分主流数据库&#xff0c;今天将介绍如何使用Python来操作MySQL数据库。 安装MySQL 首先&#xff0c;我们需要安装MySQL服务器&#xff0c;可以从MyS…...

netty群聊系统

1设计思路&#xff1a;启动一个服务端&#xff0c;多个客户端第一个客户端启动时&#xff0c;会告诉服务器上线了第二个客户端启动时&#xff0c;告诉服务器上线&#xff0c;并且通知第一个启动的客户端第三个客户端启动时&#xff0c;告诉服务器上线&#xff0c;并且通知第一个…...

Android 初代 K-V 存储框架 SharedPreferences,旧时代的余晖?

本文已收录到 AndroidFamily&#xff0c;技术和职场问题&#xff0c;请关注公众号 [彭旭锐] 提问。 前言 大家好&#xff0c;我是小彭。 SharedPreferences 是 Android 平台上轻量级的 K-V 存储框架&#xff0c;亦是初代 K-V 存储框架&#xff0c;至今被很多应用沿用。 有的…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...