【leetcode hot 100 138】随机链表的复制

解决一:回溯 + 哈希表

本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表,我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在,当我们拷贝节点时,「当前节点的随机指针指向的节点」可能还没创建,因此我们需要变换思路。一个可行方案是,我们利用回溯的方式,让每个节点的拷贝操作相互独立。对于当前节点,我们首先要进行拷贝,然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝,拷贝完成后将创建的新节点的指针返回,即可完成当前节点的两指针的赋值。

具体地,我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中,我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建,我们都立刻递归地进行创建。当我们拷贝完成,回溯到当前层时,我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向,因此我们可能递归地多次尝试拷贝某个节点,为了防止重复拷贝,我们需要首先检查当前节点是否被拷贝过,如果已经拷贝过,我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

/*
// 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;}
}
*/class Solution {// <旧的node,新的node>Map<Node,Node> newNodeMap = new HashMap<>(); public Node copyRandomList(Node head) {if(head == null){return null;}if(!newNodeMap.containsKey(head)){// 有旧node,但是没有新nodeNode newNode = new Node(head.val);   // 注意上述构造函数newNodeMap.put(head, newNode);  // 要放在两个copyRandomList之上,否则后面会连续创建最终导致栈溢出newNode.next = copyRandomList(head.next);newNode.random = copyRandomList(head.random);}// return newNode;不可以,这是一个临时变量return newNodeMap.get(head);}
}

注意:

  • return newNodeMap.get(head);,不可以return newNode;,因为这是一个这是一个临时变量。
  • newNodeMap.put(head, newNode);要放在两个copyRandomList之上,否则后面会连续创建最终导致栈溢出;且后面的复制是地址赋值,就算先put了也会影响已经put的元素

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/31618.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java 集合框架大师课:集合框架源码解剖室(五)

&#x1f525;Java 集合框架大师课&#xff1a;集合框架源码解剖室&#xff08;五&#xff09; &#x1f4a3; 警告&#xff1a;本章包含大量 裸码级硬核分析&#xff0c;建议搭配咖啡因饮料阅读&#xff01;☕️ 第一章 ArrayList 的扩容玄学 1.1 动态扩容核心代码大卸八块 …

Kubernetes服务部署 —— Kafka

1、简介 Kafka和zookeeper是两种典型的有状态的应用集群服务。首先kafka和zookeeper都需要存储盘来保存有状态信息&#xff1b;其次kafka和zookeeper每一个实例都需要有对应的实例Id (Kafka需broker.id, zookeeper需要my.id) 来作为集群内部每个成员的标识&#xff0c;集群内节…

计算机网络基础知识

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…

电脑的写字板如何使用?

打开写字板&#xff1a; 直接按一下键盘上的win R 键&#xff0c;然后输入&#xff1a;write &#xff0c; 再按一下回车 , 即可打开写字板 可以在里面写文字 和 插入图片等… &#xff0c; 如下所示&#xff1a; 保存写字板内容&#xff1a; 当我们写好了之后&#xff0c;…

用vector实现栈的功能

要注意pop_back和back()的区别 #include <bits/stdc.h> using namespace std;void Push(vector<int> &v,int x) {v.push_back(x); }void Top(vector<int> &v) {if(!v.empty()){cout<<v.back()<<endl;// v.pop_back();}else {cout<&l…

SegMAN模型详解及代码复现

SegMAN模型概述 模型背景 在深入探讨SegMAN模型之前&#xff0c;我们需要了解其研究背景。在SegMAN出现之前&#xff0c;计算机视觉领域的研究主要集中在以下几个方面&#xff1a; 手工制作方法&#xff0c;如SIFT基于卷积神经网络(CNN)的方法&#xff0c;如STN和PTN对平移、…

基于粒子群算法的配电网重构

一、配电网重构原理 定义&#xff1a; 配电网重构是指在满足运行约束的前提下&#xff0c;通过改变开关状态优化配电网性能&#xff0c;提高系统的经济效益和运行效率。 拓扑约束&#xff1a; 配电网必须保持径向拓扑&#xff0c;避免环网或孤岛。采用算法控制开关状态的选择&…

自然语言处理:无监督朴素贝叶斯模型

介绍 大家好&#xff0c;博主又来和大家分享自然语言处理领域的知识了&#xff0c;今天给大家介绍的是无监督朴素贝叶斯模型。 在自然语言处理这个充满挑战又极具魅力的领域&#xff0c;如何从海量的文本数据中挖掘有价值的信息&#xff0c;一直是研究者们不断探索的课题。无…

软件工程概述

软件开发生命周期 软件定义时期&#xff1a;包括可行性研究和详细需求分析&#xff0c;任务是确定软件开发的总目标。 问题定义可行性研究&#xff08;经济、技术、操作、社会可行性&#xff0c;确定问题和解决办法&#xff09;需求分析&#xff08;确定功能需求&#xff0c;性…

基于51单片机的日历流水灯proteus仿真

地址&#xff1a; https://pan.baidu.com/s/1lt1ubDhKNTeIcP0Kf1UXrA 提取码&#xff1a;1234 仿真图&#xff1a; 芯片/模块的特点&#xff1a; AT89C52/AT89C51简介&#xff1a; AT89C51 是一款常用的 8 位单片机&#xff0c;由 Atmel 公司&#xff08;现已被 Microchip 收…

【Go沉思录】朝花夕拾:探究 Go 接口型函数

本文目录 序1.接口型函数案例方式1 GetterFunc 类型的函数作为参数方式2 实现了 Getter 接口的结构体作为参数价值 2.net/http包中的使用场景 序 之前写Geecache的时候&#xff0c;遇到了接口型函数&#xff0c;当时没有搞懂&#xff0c;现在重新回过头研究复习Geecache的时候…

【若依框架】代码生成详细教程,15分钟搭建Springboot+Vue3前后端分离项目,基于Mysql8数据库和Redis5,管理后台前端基于Vue3和Element Plus,开发小程序数据后台

今天我们来借助若依来快速的搭建一个基于springboot的Java管理后台&#xff0c;后台网页使用vue3和 Element Plus来快速搭建。这里我们可以借助若依自动生成Java和vue3代码&#xff0c;这就是若依的强大之处&#xff0c;即便你不会Java和vue开发&#xff0c;只要跟着石头哥也可…

Java 线程与线程池类/接口继承谱系图+核心方法详解

Java 线程与线程池类/接口继承谱系图 1. 线程相关类与接口关系 #mermaid-svg-shTOx2cIkm79Zevf {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-shTOx2cIkm79Zevf .error-icon{fill:#552222;}#mermaid-svg-shTOx2cI…

BFS(十三)463. 岛屿的周长

463. 岛屿的周长 给定一个 row x col 的二维网格地图 grid &#xff0c;其中&#xff1a;grid[i][j] 1 表示陆地&#xff0c; grid[i][j] 0 表示水域。 网格中的格子 水平和垂直 方向相连&#xff08;对角线方向不相连&#xff09;。整个网格被水完全包围&#xff0c;但其中恰…

使用 Ansys Mechanical 和 optiSLang 进行材料模型校准

介绍 提供与实验数据匹配的准确仿真结果的材料模型是成功对实际应用进行 FEA 仿真的基础。根据实验数据校准材料模型是一个优化问题&#xff0c;其中仿真和真值信号之间的“距离”最小&#xff0c;表明模型与实验的“接近”程度。在此示例中&#xff0c;我们将对校准示例进行概…

SSA-朴素贝叶斯分类预测matlab代码

麻雀搜索算法&#xff08;Sparrow Search Algorithm&#xff0c;简称 SSA&#xff09;是于 2020 年提出的一种新兴群智能优化算法&#xff0c;其灵感主要来源于麻雀的觅食行为以及反捕食行为。 本次使用的数据是 Excel 格式的分类数据集数据。数据集被合理划分为训练集、验证集…

Houdini SOP层 Scatter节点

SOP 代表 Surface Operator&#xff08;几何体操作节点&#xff09;&#xff0c;所有几何体的建模、变形、分布等操作都在此层级完成。 Scatter节点的作用就是 以不同的密度在模型表面撒点 Scatter 节点属于 SOP&#xff08;几何体&#xff09;层级&#xff1a; 进入 Geometr…

数据结构:有序表的合并

前文介绍了《有序表的插入》&#xff0c;本文介绍有序表的合并。这两种对有序表的操作&#xff0c;是数据结构中常考的内容&#xff0c;特别是在 408 考卷中&#xff0c;在算法设计的题目中&#xff0c;有可能会考查对有序表的操作。那么&#xff0c;这两篇文章中的方法就是能够…

STM32Cubemx-H7-8-维特科技WT61C-TTL陀螺仪获取XYZ角度

前言 本人玩车的时候要用到陀螺仪 MPU6050容易卡死&#xff0c;然后还很漂&#xff0c;还是太难用了 68块钱的陀螺仪再上位机上的效果挺满意&#xff0c;于是打算用串口用到自己的模型上 本文教大家如何编写串口程序&#xff0c;通过串口获取角度 大家把本文的原理学会后&…

本地部署Navidrome个人云音乐平台随时随地畅听本地音乐文件

文章目录 前言1. 安装Docker2. 创建并启动Navidrome容器3. 公网远程访问本地Navidrome3.1 内网穿透工具安装3.2 创建远程连接公网地址3.3 使用固定公网地址远程访问 前言 今天我要给大家安利一个超酷的私有化音乐神器——Navidrome&#xff01;它不仅让你随时随地畅享本地音乐…