当前位置: 首页 > 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;至今被很多应用沿用。 有的…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

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

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

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

React核心概念:State是什么?如何用useState管理组件自己的数据?

系列回顾&#xff1a; 在上一篇《React入门第一步》中&#xff0c;我们已经成功创建并运行了第一个React项目。我们学会了用Vite初始化项目&#xff0c;并修改了App.jsx组件&#xff0c;让页面显示出我们想要的文字。但是&#xff0c;那个页面是“死”的&#xff0c;它只是静态…...

跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践

在电商行业蓬勃发展的当下&#xff0c;多平台运营已成为众多商家的必然选择。然而&#xff0c;不同电商平台在商品数据接口方面存在差异&#xff0c;导致商家在跨平台运营时面临诸多挑战&#xff0c;如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

GAN模式奔溃的探讨论文综述(一)

简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...

高效的后台管理系统——可进行二次开发

随着互联网技术的迅猛发展&#xff0c;企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心&#xff0c;成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统&#xff0c;它不仅支持跨平台应用&#xff0c;还能提供丰富…...

C++ Saucer 编写Windows桌面应用

文章目录 一、背景二、Saucer 简介核心特性典型应用场景 三、生成自己的项目四、以Win32项目方式构建Win32项目禁用最大化按钮 五、总结 一、背景 使用Saucer框架&#xff0c;开发Windows桌面应用&#xff0c;把一个html页面作为GUI设计放到Saucer里&#xff0c;隐藏掉运行时弹…...