138. 随机链表的复制 --力扣 --JAVA
题目
给你一个长度为
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作为传入参数。
解题思路
- 先排除特殊情况:若链表为null则直接返回null;
- 使用Map存储原始链表的节点和对应索引;
- 使用List来存储复制后链表的节点;
- while循环完成节点复制、next链接和存储;
- 从Map和List中获取首节点进行第二次遍历;
- 第二次遍历建立random链接。
代码展示
class Solution {public Node copyRandomList(Node head) {//排除特殊情况if (head == null){return null;}Node ans = new Node(head.val);//需要获取random的索引,所以用map比遍历List要便捷Map<Node, Integer> headMap = new HashMap<>();//只需要根据索引获取对应节点,List本身是有序的,所以不需要用MapList<Node> ansList = new ArrayList<>();int index = 0;headMap.put(head, index);ansList.add(ans);//遍历生成所有节点并存储起来while (head.next != null){head = head.next;ans.next = new Node(head.val);index++;headMap.put(head, index);ansList.add(ans.next);ans = ans.next;}for (Node node : headMap.keySet()){if(headMap.get(node) == 0){head = node;break;}}ans = ansList.get(0);while (head != null && ans != null){Integer num = headMap.get(head.random);Node temp = null;if(num != null){temp = ansList.get(num);}ans.random = temp;head = head.next;ans = ans.next;}return ansList.get(0);}
}
相关文章:
138. 随机链表的复制 --力扣 --JAVA
题目 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点…...
Python Flask 框架开发
1. Python 代码示例(使用 Flask 框架) 1.1 安装依赖库 pip install flask flask_sqlalchemy flask_login flask_wtf 1.2 主应用文件 app.py from flask import Flask, request, jsonify, redirect, url_for, render_template, flash from flask_sqla…...
k8s安装-学习环境
目录 环境准备 配置hosts 关闭防火墙 关闭交换分区 调整swappiness参数 关闭setlinux Ipv4转发 时钟同步 安装Docker 配置Yum源 安装 配置 启动 日志 安装k8s 配置Yum源 Master节点 安装 初始化 配置kubectl 部署CNI网络插件 Node节点 检查 环境准备 准…...
Vue3动态表单
示例代码如下: // 引入需要的依赖包 import { ref, reactive } from vue; import { useForm } from /composables/useForm;// 定义表单数据模型 const formModel reactive({name: ,age: ,gender: , });// 使用自定义的useForm函数创建表单实例 const { register, …...
2312skia,15vulkan及技巧
ANGLE介绍 ANGLE,把OpenGLES2或3调用转换为DirectX9,11或OpenGL调用.这些说明记录了如何在Windows或Linux上使用ANGLE而不是本地OpenGL后端. 细节 gclient sync下载ANGLE的源码及Skia的其他仅测试依赖项. 要针对ANGLE构建Skia测试工具,请添加skia_use_angletrue到args.gn文件…...
TLSF算法概念,原理,内存碎片问题分析
TLSF算法介绍 TLSF(Two-Level Segregated Fit,两级分割适应算法)。 第一级(first level,简称fl):将内存大小按2的幂次方划分一个粗粒度的范围,如一个72字节的空闲内存的fl是6(72介…...
sharding-jdbc实现分库分表
shigen日更文章的博客写手,擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长,分享认知,留住感动。 😅😅最近几天的状态有点不对,所以有几天没有更新了。 当我们的数据量比较大…...
JDK中lock锁的机制,其底层是一种无锁的架构实现的,公平锁和非公平锁
简述JDK中lock锁的机制,其底层是一种无锁的架构实现的,是否知道其是如何实现的 synchronized与lock lock是一个接口,而synchronized是在JVM层面实现的。synchronized释放锁有两种方式: 获取锁的线程执行完同步代码,…...
c++通过serial库进行上下位机通信
编辑 风紊 现役大学牲,半退休robomaster视觉队员 写在前面 本文章主要介绍的是如何通过开源的serial库和虚拟串口实现上位机和下位机通信。 需求 假设下位机有这样一个数据报发送给上位机 struct DataRecv {char start s;TeamColor color TeamColor::Blu…...
【傻瓜级JS-DLL-WINCC-PLC交互】7.C#直连PLC并读取PLC数据
思路 JS-DLL-WINCC-PLC之间进行交互,思路,先用Visual Studio创建一个C#的DLL控件,然后这个控件里面嵌入浏览器组件,实现JS与DLL通信,然后DLL放入到WINCC里面的图形编辑器中,实现DLL与WINCC的通信。然后PLC与…...
指针常量和常量指针的区别
文章目录 指针常量常量指针即是指针常量又是常量指针 指针常量 指针常量的本质是常量,表示的是 这个指针所指向的地址不能发生改变。即指针变量的值(即地址值)不能发生修改。但是指针所指向的那块内存里的值是可以修改的。 注意:…...
离散化算法总结
离散化是将大范围的数字映射到小范围的区间内,适用于稀疏的区间。 两个问题需要考虑: 1. 原数组中可能有重复元素,需要去重。 2. 如何算出离散化后的值(离散化后保序,使用二分)。 题目链接: …...
【海思SS528 | VO】MPP媒体处理软件V5.0 | VO模块编程总结
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 🤣本文内容🤣&a…...
逻辑卷管理器lvm
啥意思,个人理解就是可以将物理分区合并一起组成大的磁盘,也可以移除其中的某个分区。 有四个概念需要了解下 PV,物理卷,VG 卷用户组,PE物理扩展块,LV逻辑卷 p物理,v卷,g用户组&a…...
函数声明后的“ - >”是什么?
这种语法的优势之一是可以在函数的返回类型中使用函数参数,使得返回类型更灵活。 先来看一个使用尾返回类型的例子: #include <iostream> auto add(int a, int b) -> int {return a b; }int main() {std::cout << add(3, 4) <<…...
51爱心流水灯32灯炫酷代码
源代码摘自远眺883的文章,大佬是30个灯的,感兴趣的铁汁们可以去看看哦~(已取得原作者的许可):基于STC89C51单片机设计的心形流水灯软件代码部分_单片机流水灯代码_远眺883的博客-CSDN博客 由于博主是个小菜鸡ÿ…...
将不同时间点的登录状态记录转化为不同时间段的相同登录状态SQL求解
题目 有不同时间点的登录状态记录表state_log如下 请使用sql将其转化为如下表的不同时间段的相同登录状态记录 思路分析: 此类问题需要用到lag或lead函数取上下行对应的数据,然后对前后结果做比较打标签(0或1),再…...
正则表达式与SQL数据库教程
使用正则表达式通过用例查询 Postgres 数据库: 正则表达式(又名 Regex) 正则表达式是一个强大的工具,广泛用于模式匹配和文本操作。 几乎所有编程语言都支持它们,并且经常用于文本提取、搜索和匹配文本等用例。 正则…...
HTML_web扩展标签
1.表格标签 2.增强表头表现 4.表格属性(实际不常用) 结构标签: 合并单元格: 更多请查看主页...
论文阅读:Distributed Initialization for VVIRO with Position-Unknown UWB Network
前言 Distributed Initialization for Visual-Inertial-Ranging Odometry with Position-Unknown UWB Network这篇论文是发表在ICRA 2023上的一篇文章,本文提出了一种基于位置未知UWB网络的一致性视觉惯性紧耦合优化测距算法( DC-VIRO )的分布式初始化方法。 对于…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
