从零学算法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…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
网页端 js 读取发票里的二维码信息(图片和PDF格式)
起因 为了实现在报销流程中,发票不能重用的限制,发票上传后,希望能读出发票号,并记录发票号已用,下次不再可用于报销。 基于上面的需求,研究了OCR 的方式和读PDF的方式,实际是可行的ÿ…...
背包问题双雄:01 背包与完全背包详解(Java 实现)
一、背包问题概述 背包问题是动态规划领域的经典问题,其核心在于如何在有限容量的背包中选择物品,使得总价值最大化。根据物品选择规则的不同,主要分为两类: 01 背包:每件物品最多选 1 次(选或不选&#…...
云原生时代的系统设计:架构转型的战略支点
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、云原生的崛起:技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深,传统的 I…...
