Leetcode 3.12
leetcode hot 100
- 链表
- 1.两两交换链表中的节点
- 2.随机链表的复制
- 3.排序链表
链表
1.两两交换链表中的节点
两两交换链表中的节点

- 1.必须要设置一个dummy (temp) 结点
- 2.保存第二个节点
- 3.先让第一个节点指向第三个节点
- 4.再让第二个节点指向第一个节点
- 5.最后让dummy指向第二个节点
- 6.更新dummy节点,和当前节点
- 7.尝试了以下,以上交换的步骤3-5可以任意修改顺序
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* p = head;ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* ans = dummy;int i = 0;while (p != nullptr && p->next != nullptr) {//保存第二个节点auto tmp = p->next;//第一个节点指向第三个节点p->next = tmp->next;//第二个节点指向第一个节点tmp->next = p;//dummy指向第二个节点dummy->next = tmp;//更新指针dummy = p;p = p->next;}return ans->next;}
};
2.随机链表的复制
随机链表的复制
-
两个循环
-
先用一个循环,用unordered_map把两个链表捆绑
-
再用一个循环构建新链表的引用指向
- 建立新的next和random指向
- mp[q]->next = mp[q->next]
- mp[q]->random = mp[q->random]
- 遍历至原链表下一节点
- 建立新的next和random指向
-
mp[head] 就是新链表的头节点

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {unordered_map<Node*, Node*> mp;Node* p = head;//绑定链表while (p != nullptr) {mp[p] = new Node(p->val);p = p->next;}Node* q = head;//建立新的引用指向while (q != nullptr) {mp[q]->next = mp[q->next];mp[q]->random = mp[q->random];q = q->next;}return mp[head];}
};
3.排序链表
排序链表
放入vector,排序后覆盖原数组……开个玩笑,来看官解吧:
-
找到链表中点。
- 快指针 = head->next, 慢指针 = slow->next
- 快指针走两步,慢指针走一步,快指针到末尾时慢指针为链表中点
- 找到中点 slow 后,执行 slow.next = nullptr 将链表切断
- 递归分割时,输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp (因为链表是从 slow 切断的)。
- cut 递归终止条件: 当 head.next == nullptr 时,说明只有一个节点了,直接返回此节点。
-
将两个子链表排序合并,这里可以用到合并两个有序链表
-
双指针法合并,建立辅助 ListNode* dummy 作为头部。
-
设置两指针 left, right 分别指向两链表头部,比较两指针处节点值大小,由小到大加入合并链表头部,指针交替前进,直至添加完两个链表。
-
-
返回辅助ListNode dummy作为头部的下个节点 h.next。
时间复杂度:O(nlogn),其中 n 是链表的长度。
空间复杂度:O(logn),其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode* fast = head->next, *slow = head;while (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;}ListNode* tmp = slow->next;slow->next = nullptr;ListNode* left = sortList(head);ListNode* right = sortList(tmp);ListNode* dummy = new ListNode(0);ListNode* ans = dummy;while (left != nullptr && right != nullptr) {if (left->val > right->val) {ans->next = right;right = right->next;} else {ans->next = left;left = left->next;}ans = ans->next;}ans->next = left == nullptr ? right : left;return dummy->next;}
};
相关文章:
Leetcode 3.12
leetcode hot 100 链表1.两两交换链表中的节点2.随机链表的复制3.排序链表 链表 1.两两交换链表中的节点 两两交换链表中的节点 1.必须要设置一个dummy (temp) 结点2.保存第二个节点3.先让第一个节点指向第三个节点4.再让第二个节点指向第一个节点5.最后让dummy指向第二个节点…...
【天池课堂】零基础入门数据挖掘-课程汇总
写在前面: 如果你现在很迷茫,但是又对数据挖掘感兴趣,建议先看看以下两个视频直播,两位大佬亲身讲述自己和数据挖掘的前世今生。 《如何入门数据挖掘竞赛》 鱼遇雨欲语与余。天池明星选手,武汉大学硕士,天…...
表单进阶(3)-上传文件和隐藏字段
上传文件:<input type"file"> 隐藏字段:<input type"hidden" name"" id"" value"带给后端的信息"> 禁用disabled:<button disabled"disabled">注册</bu…...
LLM(大语言模型)常用评测指标-MAP@R
MAPR (Mean Average Precision at R) 是一种用于评估信息检索系统或排序模型效果的评价指标。它特别适用于那些返回一组相关结果的情况,例如搜索引擎或推荐系统。这里的“R”代表返回的相关结果的数量。MAPR 考虑了结果的排名和相关性两个因素。 计算方法 计算平…...
腾讯面经学习笔记
💖 前言 👩🏫 参考地址 💖 操作系统 1. 进程和线程的区别 本质区别 进程是操作系统资源分配的基本单位线程是任务调度和执行的基本单位 开销方面 每个进程都有独立的代码和数据空间(程序上下文)&#…...
北京某中厂凉经
3月12号 大二想着找一份暑假面试,然后就海投。北京某上市公司给了面试,这也是我的第一个面试,听面试官最后的话大概是挂了。 大概回忆一下当时面试的部分内容吧,虽然已经过去一两小时的,而且我属于那种一面完就忘的差…...
离线数仓(五)【数据仓库建模】
前言 今天开始正式数据仓库的内容了, 前面我们把生产数据 , 数据上传到 HDFS , Kafka 的通道都已经搭建完毕了, 数据也就正式进入数据仓库了, 解下来的数仓建模是重中之重 , 是将来吃饭的家伙 ! 以及 Hive SQL 必须熟练到像喝水一样 ! 第1章 数据仓库概述 1.1 数据仓库概念 数…...
python | 类与对象
在 Python 中,我们用关键字 class 来定义类: class Player:pass Player 类中只有一条语句 pass,这是 Python 中的特殊语句,没有实际含义。 Python 在执行到它时也什么都不会做。不过它能够保证结构的完整性。例如,我…...
基于Qt 和python 的自动升级功能
需求: 公司内部的一个客户端工具,想加上一个自动升级功能。 服务端: 1,服务端使用python3.7 ,搭配 fastapi 和uvicorn 写一个简单的服务,开出一个get接口,用于客户端读取安装包的版本&#…...
【论文阅读】IEEE Access 2019 BadNets:评估深度神经网络的后门攻击
文章目录 一.论文信息二.论文内容1.摘要2.引言3.主要图表4.结论 一.论文信息 论文题目: BadNets: Evaluating Backdooring Attacks on Deep Neural Networks(BadNets:评估深度神经网络的后门攻击) 论文来源: 2019-IEEE Access …...
Unity 让角色动起来(动画控制器)
下载素材: 导入后,找到预制体和动画。 新建动画控制器,拖动到预制体的新版动画组件上。 建立动画关系 创建脚本,挂载到预制体上。 using System.Collections; using System.Collections.Generic; using UnityEngine;public c…...
ubuntu22.04环境中安装pylint
ubuntu22.04环境中安装pylint sudo apt-get install python3-pipsudo aptitude install python3-pipsudo pip install pylint sudo apt-get install python3-pip 在安装pylint的时候,需要使用pip命令,在ubuntu22.04环境中命令如下: $ sudo …...
主流数据库的区别
几个主流的数据库有: 1. MySQL:MySQL是一种关系型数据库管理系统,常用于Web应用程序开发和数据存储。 2. Oracle:Oracle是一种关系型数据库管理系统,由Oracle Corporation开发和销售。它广泛用于企业级应用程序中。 …...
veeam备份基础
veeam的安装 将文件动态连接文件复制到veeam的安装目录中,替换掉新的文件 重新启动服务 为veeam添加证书 为veeam添加存储 其他 第一次完整备份时间会比较久 备份预览,transferred和processing date的区别 transferred后面数据为压缩比...
Flink并行度
1、Task flink中每个算子就是一个Task,比如flatMap、map、sum是一个Task。 2、SubTask 算子有几个并行度SubTask的数量就是几,比如 3、算子并行度 算子并行度指的是每个算子的并行度,可用env.setParallelism(1);设置所有算子的并行度&am…...
这届留学生是懂作弊的,ChatGPT震惊教授一整年!
ChatGPT,一款全新聊天机器人模型,成为北美科技圈的新时髦。 图片来源:New York Post 有人和它“探讨”人生,畅聊哲学,但也有人起了歪心思,用它进行学术作弊。这类新型学术不端事件引发人们关于教育的再思考…...
CVE-2023-38836 BoidCMSv.2.0.0 后台文件上传漏洞
漏洞简介 BoidCMS是一个免费的开源平面文件 CMS,用于构建简单的网站和博客,使用 PHP 开发并使用 JSON 作为数据库。它的安装无需配置或安装任何关系数据库(如 MySQL)。您只需要一个支持PHP 的Web服务器。在 BoidCMS v.2.0.0 中存…...
pf4j插件实践验证
Java系统实现插件机制,可自行通过classloader实现,亦可使用成熟的框架。pf4j是一款轻量级,扩展性强的插件,可实现插件的开发管理(插件开发、加载、卸载、更新),省略了一些基础代码的开发&#x…...
计算机组成原理之运算方法和运算器
文章目录 数据格式定点数浮点数 机器码表示原码反码补码数的补码与真值 移码IEEE754标准 数据格式 定点数 定点数就是数据的小数点的位置是固定不变的,通常将数据表示成纯小数或纯整数以 n 1 n1 n1 位数表示定点数,以 X n Xn Xn表示定点数的正负&#…...
Redux Toolkit
本文作者为 360 奇舞团前端开发工程师 阅读本文章前,需要先了解下 redux 的基本概念与用法,Redux Toolkit 是建立在 Redux 基础之上的工具包,因此需要对 Redux 的基本概念有一定的了解,包括 Action、Reducer、Store、Middleware 等…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
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...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
