当前位置: 首页 > 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…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...