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

从零学算法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 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成&#xff0c;其中每个新节点的值都设为其对应的原节点的值。新节…...

CTF PWN练习之返回地址覆盖

今天进行的实验是CTF PWN练习之返回地址覆盖&#xff0c;来体验一下新的溢出方式。 学习地址覆盖之前还有些小知识需要掌握&#xff0c;不然做题的时候你肯定一脸懵逼,首先是函数调用约定&#xff0c;然后还要知道基本的缓冲区溢出攻击模型。 函数调用约定 函数调用约定描述…...

OpenCV中图像变换

一、介绍 transform()&#xff1a;Transposes a matrix. perspectiveTransform()&#xff1a;Performs the perspective matrix transformation of vectors. warpAffine()&#xff1a;Applies an affine transformation to an image. warpPerspective()&#xff1a;Applies a p…...

wordpress发表文章时报错: rest_cannot_create,抱歉,您不能为此用户创建文章(已解决)

使用wordpress 的rest api发布文章&#xff0c;首先使用wp-json/jwt-auth/v1/token接口获取token&#xff0c;然后再使用/wp-json/wp/v2/posts 接口发表文章&#xff0c;但是使用axios请求时&#xff0c;却报错&#xff1a; 但是&#xff0c;我在postman上却是可以的&#xff0…...

数学建模学习(7):Matlab绘图

一、二维图像绘制 1.绘制曲线图 最基础的二维图形绘制方法&#xff1a;plot -plot命令自动打开一个图形窗口Figure&#xff1b; 用直线连接相邻两数据点来绘制图形 -根据图形坐标大小自动缩扩坐标轴&#xff0c;将数据标尺及单位标注自动加到两个坐标轴上&#xff0c;可自定…...

CSS中所有选择器详解

文章目录 一、基础选择器1.标签选择器2.类选择器3.id选择器4.通配符选择器 二、复合选择器1.交集选择器2.并集选择器 三、属性选择器1.[属性]2.[属性属性值]3.[属性^属性值]4.[属性$属性值]5.[属性*属性值] 四、关系选择器1.父亲>儿子2.祖先 后代3.兄弟4.兄~弟 五、伪类选择…...

STM32 低功耗学习

STM32 电源系统结构介绍 电源系统&#xff1a;VDDA供电区域、VDD供电区域、1.8V供电区域、后备供电区域。 器件的工作电压&#xff08;VDD&#xff09;2.0~3.6V 为了提高转换精度&#xff0c;给模拟外设独立供电。电压调节器为1.8V供电区域供电&#xff0c;且1.8V供电区域是电…...

HCIP--云计算题库 V5.0版本

在国家政策的支持下&#xff0c;我国云计算应用市场发展明显加快&#xff0c;越来越多的企业开始介入云产业&#xff0c;出现了大量的应用解决方案&#xff0c;云应用的成功案例逐渐丰富&#xff0c;用户了解和认可程度不断提高&#xff0c;云计算产业发展迎来了“黄金机遇期”…...

小白到运维工程师自学之路 第六十五集 (docker-compose)

一、概述 Docker Compose 的前身是 Fig&#xff0c;它是一个定义及运行多个 Docker 容器的工具。可以使用YAML文件来配置应用程序的服务。然后&#xff0c;使用单个命令&#xff0c;您可以创建并启动配置中的所有服务。Docker Compose 会通过解析容器间的依赖关系&#xff08;…...

量子机器学习

量子机器学习(QML)是结合量子计算和机器学习的交叉领域&#xff0c;旨在利用量子计算的优势来改进机器学习算法的性能。下面是一些有关量子机器学习的学习资源和技术应用&#xff1a; 学术论文和研究资料&#xff1a; ArXiv.org&#xff1a;在ArXiv的量子物理和机器学习类别中&…...

WEB集群——tomcat

1. 简述静态网页和动态网页的区别。 2. 简述 Webl.0 和 Web2.0 的区别。 3. 安装tomcat8&#xff0c;配置服务启动脚本&#xff0c;部署jpress应用。 一、简述静态网页和动态网页的区别 &#xff08;1&#xff09;静态网页 1.什么是静态网页 请求响应信息&#xff0c;发…...

Vulnhub: blogger:1靶机

kali&#xff1a;192.168.111.111 靶机&#xff1a;192.168.111.176 信息收集 端口扫描 nmap -A -sC -v -sV -T5 -p- --scripthttp-enum 192.168.111.176 在80端口的/assets/fonts/目录下发现blog目录&#xff0c;访问后发现为wordpress 利用wpscan发现wordpress插件wpdisc…...

老版MFC工程迁移到VC2019编译EXE太大的问题

有个老版静态链接MFC库的MFC程序需要迁移到VC2019编译&#xff0c;直接用VC2019打开就会自动迁移过去&#xff0c;然后编译一下&#xff0c;生成的EXE大小将近3MB&#xff0c;老版的工程编译出来也就600多KB。 肯定哪里不对劲&#xff01; 好一顿研究之后发现原来默认会把MFC…...

Curve深陷安全事件,OKLink如何破局

出品&#xff5c;欧科云链研究院 作者&#xff5c;Matthew Lee 7月31号&#xff0c;Curve 在平台表示 Vyper 0.2.15 的稳定币池由于编译器的漏洞所以遭到攻击。具体因为重入锁功能的失效&#xff0c;所以黑客可以轻易发动重入攻击&#xff0c;即允许攻击者在单次交易中执行某…...

2023华数杯数学建模思路A题B题C题模型代码分析

目录 一.2023华数杯数学建模最新思路&#xff1a;比赛开始后第一时间更新 更新查看文末名片 二.往年华数杯赛题简介分析&#xff1a; 一.2023华数杯数学建模最新思路&#xff1a;比赛开始后第一时间更新 更新查看文末名片 二.往年华数杯赛题简介分析&#xff1a; 2022华数杯…...

el-table合并单元格

el-tabel数据结构 此处为this.rolePermitItemList 合并后的样式&#xff1a; el-table-column 需要添加property字段&#xff0c;属性值同props&#xff0c;用来判断需要合并的字段 <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

使用消息队列&#xff0c;我们肯定希望不丢消息&#xff0c;也就是消息队列组件&#xff0c;需要保证消息的可靠交付。消息交付的可靠性保障&#xff0c;有以下三种承诺&#xff1a; 最多一次&#xff08;at most once&#xff09;&#xff1a;消息可能会丢失&#xff0c;但绝…...

Doris(三)-集群部署3个FE+3个BE

前置 1&#xff09;配置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…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

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...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...

Python的__call__ 方法

在 Python 中&#xff0c;__call__ 是一个特殊的魔术方法&#xff08;magic method&#xff09;&#xff0c;它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时&#xff08;例如 obj()&#xff09;&#xff0c;Python 会自动调用该对象的 __call__ 方法…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...