剑指 Offer Day2——链表(简单)
目录
- 剑指 Offer 06. 从尾到头打印链表
- 剑指 Offer 24. 反转链表
- 剑指 Offer 35. 复杂链表的复制
剑指 Offer 06. 从尾到头打印链表
原题链接:06. 从尾到头打印链表
最容易想到的思路就是先从头到尾打印下来,然后 reverse 一下,但这里我们使用递归。
class Solution {
public:vector<int> reversePrint(ListNode *head) {if (head == nullptr) return {};auto res = reversePrint(head->next);res.push_back(head->val);return res;}
};
递归的缺点是元素一多容易爆栈,我们还可以利用栈的特性来完成这道题。
剑指 Offer 24. 反转链表
原题链接:24. 反转链表
递归解法(清晰易懂):
class Solution {
public:ListNode *reverseList(ListNode *head) {if (!head || !head->next) return head;auto newHead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newHead;}
};
当链表长度为 000 或 111 时,无需反转。
考虑链表 1→2→3→4→∅1\to2\to3\to4\to\varnothing1→2→3→4→∅,当调用 reverseList(1->next) 后,链表变成 1→2←3←41\to2\leftarrow3\leftarrow41→2←3←4,此时需要让 222 指向 111,即 2->next = 1,相当于 1->next->next = 1,之后还需要让 111 指向 ∅\varnothing∅,即 1->next = nullptr。
迭代解法:
class Solution {
public:ListNode *reverseList(ListNode *head) {ListNode *pre = nullptr;ListNode *cur = head;while (cur) {ListNode *tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}return pre;}
};
设置两个指针,每次让后一个节点指向前一个节点,然后两个指针同时右移一位。
剑指 Offer 35. 复杂链表的复制
原题链接:35. 复杂链表的复制
我们先来看一下普通链表是如何复制的。
class Node {
public:int val;Node *next;Node() : val(0), next(nullptr) {}Node(int _val) : val(_val), next(nullptr) {}Node(int _val, Node *_next) : val(_val), next(_next) {}
};class Solution {
public:Node *copyList(Node *head) {Node *cur = head;Node *dummy = new Node(-1), *pre = dummy;while (cur) {Node *newNode = new Node(cur->val);pre->next = newNode;cur = cur->next, pre = pre->next; // cur在原链表上移动,pre在新链表上移动}return dummy->next;}
};
因为普通链表只有一个 next 指针且指向下一个节点,所以我们可以用迭代的方法复制一个普通链表(当然也可以递归)。但是复杂链表还有一个 random 指针指向随机一个节点,所以迭代方法失效。
我们可以通过哈希表来建立原链表和新链表之间的对应关系,具体来说,map[原链表中的某个节点] = 新链表中相应的节点,这样就可以随机访问新链表中的节点了。
class Solution {
public:Node *copyRandomList(Node *head) {if (!head) return head;unordered_map<Node *, Node *> map;Node *cur = head;while (cur) {map[cur] = new Node(cur->val);cur = cur->next;}cur = head;while (cur) {map[cur]->next = map[cur->next];map[cur]->random = map[cur->random];cur = cur->next;}return map[head];}
};
相关文章:
剑指 Offer Day2——链表(简单)
目录剑指 Offer 06. 从尾到头打印链表剑指 Offer 24. 反转链表剑指 Offer 35. 复杂链表的复制剑指 Offer 06. 从尾到头打印链表 原题链接:06. 从尾到头打印链表 最容易想到的思路就是先从头到尾打印下来,然后 reverse 一下,但这里我们使用递归…...
Final Cut Pro 10.6.5
软件介绍Final Cut Pro 10.6.5 已通过小编安装运行测试 100%可以使用。Final Cut Pro 10.6.5 破解版启用了全新的矩形图标,与最新的macOS Ventura设计风格统一,支持最新的macOS 13 文图拉系统,支持Apple M1/M2芯片。经过完整而彻底的重新设计…...
Modelsim仿真操作指导
目录 一、前言 二、仿真分类 三、RTL级仿真 3.1创建库 3.2 仿真配置设置 3.3 运行仿真 四、常见问题 4.1 运行仿真时报错“cant read "Startup(-L)": no such element in array” 4.2 运行仿真时无任何报错,但object窗口为空,可正常运…...
你知道这20个数组方法是怎么实现的吗?
前言你们一定对JavaScript中的数组很熟悉,我们每天都会用到它的各种方法,比如push、pop、forEach、map……等等。但是仅仅使用它就足够了吗?如此出色,您一定不想停在这里。我想和你一起挑战实现20数组方法的功能。1、forEachforEa…...
《系统架构设计》-01-架构和架构师概述
文章目录1. 架构的基本定义1.1 架构组成理论1.1.1 系统元素1)概念2)静态结构和动态结构1.1.2 基本系统属性1.1.3 设计和发展原则1.2 架构的决策理论1.2.1 统一软件过程(Rational Unified Process,统一软件过程)1.2.2 决…...
第七届蓝桥杯省赛——5分小组
题目:9名运动员参加比赛,需要分3组进行预赛。有哪些分组的方案呢?我们标记运动员为 A,B,C,... I下面的程序列出了所有的分组方法。该程序的正常输出为:ABC DEF GHIABC DEG FHIABC DEH FGIABC DEI FGHABC DFG EHIABC DFH EGIABC DF…...
中国专科医院行业市场规模及未来发展趋势
中国专科医院行业市场规模及未来发展趋势中国专科医院行业在过去几年中取得了跨越式发展,市场规模不断扩大,未来的发展前景也远比过去更加乐观。根据市场调研在线网发布的2023-2029年中国专科医院行业运营现状及发展前景预测报告分析,截至2018年…...
【刷题笔记】--两数之和Ⅳ,从二叉树中找出两数之和
法一:深度搜索中序遍历双指针 思路:通过中序遍历二叉树得到一个递增的数列,再在这个递增的二叉树中找到这两数。 主要学到双指针这个方法。 对于一般数列,我们要找到两数满足其之和等于目标数,我们一般会进行暴力&a…...
浏览器渲染原理JavaScript V8引擎
浏览器渲染原理 前言 在我们面试过程中,面试官经常会问到这么一个问题,那就是从在浏览器地址栏中输入URL到页面显示,浏览器到底发生了什么? 浏览器内有哪些进程,这些进程都有些什么作用;浏览器地址输入U…...
在TheSandbox 的「BOYS PLANET」元宇宙中与你的男孩们见面吧!
世界各的男孩们成为 K-Pop 男团的旅程。 Mnet 的全球项目 BOYS PLANET 终于在 2 月 2 日首次亮相! The Sandbox 与 CJ ENM 合作,于 2 月 6 日晚上 10 点开始举办两个基于 BOYS PLANET 生存节目的虚拟体验:BOYS PLANET:BOYS LAND 和…...
数据结构与算法:java对象的比较
1.基本类型的比较 在Java中,基本类型的对象可以直接比较大小。 public class TestCompare {public static void main(String[] args) {int a 10;int b 20;System.out.println(a > b);System.out.println(a < b);System.out.println(a b);char c1 A;char…...
python(16)--类
一、类的基本操作1.定义一个类格式:class Classname( ):内容💎鄙人目前还是一名学生,最熟悉的也就是学校了,所以就以学校为例子来建立一个类吧class School():headline"帝国理工大学"def schoolmotto(self):…...
CNI 网络流量分析(七)Calico 介绍与原理(二)
文章目录CNI 网络流量分析(七)Calico 介绍与原理(二)CNIIPAM指定 IP指定非 IPAM IPCNI 网络流量分析(七)Calico 介绍与原理(二) CNI 支持多种 datapath,默认是 linuxDa…...
API安全的最大威胁:三体攻击
最近《三体》火的一塌糊涂,动画片、电视剧和书都受到了大家的喜爱。在API安全上,最近也发现了三体攻击。 当然了,肯定是不来自于三体人的攻击,这里的三体攻击指的是(trinity,也称三位一体攻击),是一个新的攻击手法。具体的情况老李也找到了相关的介绍,下面就分享给大…...
分布式事务解决方案——TCC
TCC是Try、Confirm、Cancel三个词语的缩写,TCC要求每个分支事务实现三个操作:预处理Try、确认Confirm、撤销Cancel。1、Try 阶段是做业务检查(一致性)及资源预留(隔离),此阶段仅是一个初步操作,它和后续的Confirm一起才能真正构成…...
ITSS认证分为几个级别,哪个级别最高
一、什么是ITSS ITSS( 信息技术服务标准,简称ITSS)是国内第一套成体系和综合配套的信息技术服务标准库,全面规范了IT服务产品及其组成要素,用于指导实施标准化和可信赖的IT服务。 ITSS是在工业和信息化部、国家标准化管理委员会的联合指导下…...
ZigBee案例笔记 - USART
文章目录1.串行通信接口简述2.串行通信接口寄存器U0CSR (0x86) -USART 0 控制和状态U0UCR (0xC4)–USART 0 UART 控制U0GCR (0xC5)–USART 0 通用控制U0BUF (0xC1) – USART 0 接收/传送数据缓存U0BAUD (0xC2) – USART 0 波特率控制3.设置串行通信接口比特率控制寄存器4.外设I…...
java | 基于Redis的分布式锁实现①
前言 首先,为了确保分布式锁可用,我们至少要确保锁的实现同时满足以下四个条件: 互斥性。在任意时刻,只有一个客户端能持有锁。不会发生死锁。即使有一个客户端在持有锁的期间崩溃而没有主动解锁,也能保证后续其他客户…...
十六、基于FPGA的CRC校验设计实现
1,CRC校验循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术,主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的…...
2022爱分析 · DataOps厂商全景报告 | 爱分析报告
报告编委 李喆 爱分析合伙人&首席分析师 廖耘加 爱分析分析师 目录 1. 研究范围定义 2. 市场洞察 3. 厂商全景地图 4. 市场分析与厂商评估 5. 入选厂商列表 1. 研究范围定义 研究范围 在后疫情时代,以数据分析为代表的数据消费场景日益丰富&…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
