从零学算法138
**138.**给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1:
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]
示例 3:
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]
-
/*// Definition for a Node.class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}}*/ - 我的原始人解法:先遍历一遍链表,复制出没有 random 的链表,与此同时记录下每个原结点对应的复制节点。第二轮遍历的时候复制 random 即可:
-
public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();// 头部加了一个哑结点Node node = new Node(-1);Node temp = node;Node tempHead = head;while(head!=null){node.next = new Node(head.val);map.put(head,node.next);head=head.next;node=node.next;}head = tempHead;node = temp;while(head!=null){Node random = map.get(head.random);node.next.random = random;head=head.next;node=node.next;}return temp.next;} - 或者可以像他人题解先只是创建每个节点,第二轮遍历的时候直接在 map 中把节点连起来创建链表
-
public Node copyRandomList(Node head) {if(head == null) return null;Node cur = head;Map<Node, Node> map = new HashMap<>();// 3. 复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射while(cur != null) {map.put(cur, new Node(cur.val));cur = cur.next;}cur = head;// 4. 构建新链表的 next 和 random 指向while(cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}// 5. 返回新链表的头节点return map.get(head);} - 还有个巧妙的思路,构建一个新的拼接链表为:原节点1 -> 新节点1 -> 原节点2 -> 新节点1 ->…。然后你只需要遍历这个链表,新结点的 next 就为该节点的 next 的 next,新结点的 random 就为原结点的 random 的 next。其实这也是一种原节点对应新节点的形式,只不过在 map 中表现为 key->val,在这里表现为 node -> node.next。
-
public Node copyRandomList(Node head) {if(head == null){return null;}// 暂存头结点,待会用来重新遍历Node tempHead = head;// 拼接新链表while(head != null){Node node = new Node(head.val);node.next = head.next;head.next = node;head = node.next;}// 头结点复原,再遍历一遍构建新链表 random 的指向head = tempHead;while(head != null){if(head.random != null){head.next.random = head.random.next;}head = head.next.next;}// 头结点再复原,最后遍历一遍拆分出原链表和结果链表head = tempHead;// 最后结果的头结点,下面用来遍历Node ans = head.next;// 暂存最后结果的头结点Node tempAns = ans;// 构建到尾结点就不构建了,所以是 ans.next != null,也没 next 让你继续构建了while(ans.next != null){// 或者 head.next = head.next.nexthead.next = ans.next;head = head.next;ans.next = head.next;ans = ans.next;}// 原链表尾结点复原head.next = null;return tempAns;}
相关文章:
从零学算法138
**138.**给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节…...
CTF PWN练习之返回地址覆盖
今天进行的实验是CTF PWN练习之返回地址覆盖,来体验一下新的溢出方式。 学习地址覆盖之前还有些小知识需要掌握,不然做题的时候你肯定一脸懵逼,首先是函数调用约定,然后还要知道基本的缓冲区溢出攻击模型。 函数调用约定 函数调用约定描述…...
OpenCV中图像变换
一、介绍 transform():Transposes a matrix. perspectiveTransform():Performs the perspective matrix transformation of vectors. warpAffine():Applies an affine transformation to an image. warpPerspective():Applies a p…...
wordpress发表文章时报错: rest_cannot_create,抱歉,您不能为此用户创建文章(已解决)
使用wordpress 的rest api发布文章,首先使用wp-json/jwt-auth/v1/token接口获取token,然后再使用/wp-json/wp/v2/posts 接口发表文章,但是使用axios请求时,却报错: 但是,我在postman上却是可以的࿰…...
数学建模学习(7):Matlab绘图
一、二维图像绘制 1.绘制曲线图 最基础的二维图形绘制方法:plot -plot命令自动打开一个图形窗口Figure; 用直线连接相邻两数据点来绘制图形 -根据图形坐标大小自动缩扩坐标轴,将数据标尺及单位标注自动加到两个坐标轴上,可自定…...
CSS中所有选择器详解
文章目录 一、基础选择器1.标签选择器2.类选择器3.id选择器4.通配符选择器 二、复合选择器1.交集选择器2.并集选择器 三、属性选择器1.[属性]2.[属性属性值]3.[属性^属性值]4.[属性$属性值]5.[属性*属性值] 四、关系选择器1.父亲>儿子2.祖先 后代3.兄弟4.兄~弟 五、伪类选择…...
STM32 低功耗学习
STM32 电源系统结构介绍 电源系统:VDDA供电区域、VDD供电区域、1.8V供电区域、后备供电区域。 器件的工作电压(VDD)2.0~3.6V 为了提高转换精度,给模拟外设独立供电。电压调节器为1.8V供电区域供电,且1.8V供电区域是电…...
HCIP--云计算题库 V5.0版本
在国家政策的支持下,我国云计算应用市场发展明显加快,越来越多的企业开始介入云产业,出现了大量的应用解决方案,云应用的成功案例逐渐丰富,用户了解和认可程度不断提高,云计算产业发展迎来了“黄金机遇期”…...
小白到运维工程师自学之路 第六十五集 (docker-compose)
一、概述 Docker Compose 的前身是 Fig,它是一个定义及运行多个 Docker 容器的工具。可以使用YAML文件来配置应用程序的服务。然后,使用单个命令,您可以创建并启动配置中的所有服务。Docker Compose 会通过解析容器间的依赖关系(…...
量子机器学习
量子机器学习(QML)是结合量子计算和机器学习的交叉领域,旨在利用量子计算的优势来改进机器学习算法的性能。下面是一些有关量子机器学习的学习资源和技术应用: 学术论文和研究资料: ArXiv.org:在ArXiv的量子物理和机器学习类别中&…...
WEB集群——tomcat
1. 简述静态网页和动态网页的区别。 2. 简述 Webl.0 和 Web2.0 的区别。 3. 安装tomcat8,配置服务启动脚本,部署jpress应用。 一、简述静态网页和动态网页的区别 (1)静态网页 1.什么是静态网页 请求响应信息,发…...
Vulnhub: blogger:1靶机
kali:192.168.111.111 靶机:192.168.111.176 信息收集 端口扫描 nmap -A -sC -v -sV -T5 -p- --scripthttp-enum 192.168.111.176 在80端口的/assets/fonts/目录下发现blog目录,访问后发现为wordpress 利用wpscan发现wordpress插件wpdisc…...
老版MFC工程迁移到VC2019编译EXE太大的问题
有个老版静态链接MFC库的MFC程序需要迁移到VC2019编译,直接用VC2019打开就会自动迁移过去,然后编译一下,生成的EXE大小将近3MB,老版的工程编译出来也就600多KB。 肯定哪里不对劲! 好一顿研究之后发现原来默认会把MFC…...
Curve深陷安全事件,OKLink如何破局
出品|欧科云链研究院 作者|Matthew Lee 7月31号,Curve 在平台表示 Vyper 0.2.15 的稳定币池由于编译器的漏洞所以遭到攻击。具体因为重入锁功能的失效,所以黑客可以轻易发动重入攻击,即允许攻击者在单次交易中执行某…...
2023华数杯数学建模思路A题B题C题模型代码分析
目录 一.2023华数杯数学建模最新思路:比赛开始后第一时间更新 更新查看文末名片 二.往年华数杯赛题简介分析: 一.2023华数杯数学建模最新思路:比赛开始后第一时间更新 更新查看文末名片 二.往年华数杯赛题简介分析: 2022华数杯…...
el-table合并单元格
el-tabel数据结构 此处为this.rolePermitItemList 合并后的样式: el-table-column 需要添加property字段,属性值同props,用来判断需要合并的字段 <el-table :data"rolePermitItemList" style"width: calc(100% );margi…...
html5设置不缓存
<meta http-equiv"Cache-Control" content"no-cache, no-store, must-revalidate"> <meta http-equiv"Pragma" content"no-cache"> <meta http-equiv"Expires" content"0"> 使用meta元素的htt…...
kotlin 的函数参数
https://blog.csdn.net/yoonerloop/article/details/123241451 一、无参数的函数参数 1、回调 //定义 interface OnClickListener { fun onClick() } private fun setOnClickListener(listener: OnClickListener) { } //使用 setOnClickListener(object : OnClickLi…...
谈谈 Kafka 的幂等性 Producer
使用消息队列,我们肯定希望不丢消息,也就是消息队列组件,需要保证消息的可靠交付。消息交付的可靠性保障,有以下三种承诺: 最多一次(at most once):消息可能会丢失,但绝…...
Doris(三)-集群部署3个FE+3个BE
前置 1)配置java环境 1st 解压jdk包 unzip jdk1.8.0_171-amd64.zip 2nd 配置环境变量 vim /etc/profile#文末添加JAVA_HOME/data/jdk1.8.0_171-amd64 PATH$JAVA_HOME/bin:$PATHexport PATH JAVA_HOME3rd 启用配置 source /etc/profile 4th 验证 java -versi…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Qt学习及使用_第1部分_认识Qt---Qt开发基本流程
前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...
持续交付的进化:从DevOps到AI驱动的IT新动能
文章目录 一、持续交付的本质:从手动到自动的交付飞跃关键特性案例:电商平台的高效部署 二、持续交付的演进:从CI到AI驱动的未来发展历程 中国…...
【向量库】Weaviate 搜索与索引技术:从基础概念到性能优化
文章目录 零、概述一、搜索技术分类1. 向量搜索:捕捉语义的智能检索2. 关键字搜索:精确匹配的传统方案3. 混合搜索:语义与精确的双重保障 二、向量检索技术分类1. HNSW索引:大规模数据的高效引擎2. Flat索引:小规模数据…...
ABB馈线保护 REJ601 BD446NN1XG
配电网基本量程数字继电器 REJ601是一种专用馈线保护继电器,用于保护一次和二次配电网络中的公用事业和工业电力系统。该继电器在一个单元中提供了保护和监控功能的优化组合,具有同类产品中最佳的性能和可用性。 REJ601是一种专用馈线保护继电器…...
Amazon RDS on AWS Outposts:解锁本地化云数据库的混合云新体验
在混合云架构成为企业数字化转型标配的今天,如何在本地数据中心享受云数据库的强大能力,同时满足数据本地化、低延迟访问的严苛需求?Amazon RDS on AWS Outposts 给出了完美答案——将AWS完全托管的云数据库服务无缝延伸至您的机房࿰…...
Monorepo架构: 项目管理模式对比与考量
关于 monorepo 相关概念及项目管理模式 在软件开发中,尤其是前端项目,我们会涉及到不同的项目管理模式,这里先介绍几个重要的概念“monorepo”是当前较为热门的一种项目管理方式,虽然很多人可能听说过,但可能在实际项…...
