有关链表算法

例题一

解法(模拟):
算法思路:
两个链表都是逆序存储数字的,即两个链表的个位数、⼗位数等都已经对应,可以直接相加。
在相加过程中,我们要注意是否产⽣进位,产⽣进位时需要将进位和链表数字⼀同相加。如果产⽣进位的位置在链表尾部,即答案位数⽐原链表位数⻓⼀位,还需要再 new ⼀个结点储存最⾼位。

例题二

例题三

解法:
算法思路:
画图画图画图,重要的事情说三遍~
1. 找中间节点;
2. 中间部分往后的逆序;
3. 合并两个链表

例题四

解法⼀(利⽤堆):
算法思路:
合并两个有序链表是⽐较简单且做过的,就是⽤双指针依次⽐较链表 1 、链表 2 未排序的最⼩元
素,选择更⼩的那⼀个加⼊有序的答案链表中。 合并 K 个升序链表时,我们依旧可以选择 K 个链表中,头结点值最⼩的那⼀个。那么如何快速的得到头结点最⼩的是哪⼀个呢?⽤堆这个数据结构就好啦~ 我们可以把所有的头结点放进⼀个⼩根堆中,这样就能快速的找到每次 K 个链表中,最⼩的元素是哪个。
解法⼆(递归/分治):
算法思路:
逐⼀⽐较时,答案链表越来越⻓,每个跟它合并的⼩链表的元素都需要⽐较很多次才可以成功排序。⽐如,我们有 8 个链表,每个链表⻓为 100。 逐⼀合并时,我们合并链表的⻓度分别为(0, 100), (100, 100), (200, 100), (300, 100), (400, 100), (500, 100), (600, 100), (700, 100)。所有链表的总⻓度共计 3600。 如果尽可能让⻓度相同的链表进⾏两两合并呢?这时合并链表的⻓度分别是(100, 100) x 4, (200, 200) x 2, (400, 400),共计 2400。⽐上⼀种的计算量整整少了 1/3。
迭代的做法代码细节会稍多⼀些,这⾥给出递归的实现,代码相对简洁,不易写错。
算法流程:
1. 特判,如果题⽬给出空链表,⽆需合并,直接返回;
2. 返回递归结果。
递归函数设计:
1. 递归出⼝:如果当前要合并的链表编号范围左右值相等,⽆需合并,直接返回当前链表;
2. 应⽤⼆分思想,等额划分左右两段需要合并的链表,使这两段合并后的⻓度尽可能相等;
3. 对左右两段分别递归,合并[l, r]范围内的链表;
4. 再调⽤ mergeTwoLists 函数进⾏合并(就是合并两个有序链表)

例题五

解法(模拟):
算法思路:
本题的⽬标⾮常清晰易懂,不涉及复杂的算法,只是实现过程中需要考虑的细节⽐较多。
我们可以把链表按 K 个为⼀组进⾏分组,组内进⾏反转,并且记录反转后的头尾结点,使其可以和前、后连接起来。思路⽐较简单,但是实现起来是⽐较复杂的。我们可以先求出⼀共需要逆序多少组(假设逆序 n 组),然后重复 n 次⻓度为 k 的链表的逆序即可。

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

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

相关文章

Visual Studio 2022报错c1083,win11解决办法

如果头文件报错,并且编译器报错是c1083,无法处理的时候,包括卸载重装也是无济于事的时候 此时可以采取一下办法进行修改 出现这个的主要原因是安装 Windows SDK 时版本出错,需要根据自己的 windows 版本选择安装对应版本的 Wind…

网心云邀请码:KpyV3Dk7

网心云长期有效邀请码:KpyV3Dk7 新用户注册福利码:KpyV3Dk7 通过福利码注册并登录您可获得:①可得1元收益②1张14天50%加成卡③绑定设备可得1~5元不等 新手解答: 1. 有哪些设备可以安装?闲置电脑、闲置手机、闲置平…

就业班 第二阶段 2401--3.29 day9 shell之正则+数组

九、shell 编程-数组 普通数组:只能用整数作为数组的索引 关联数组:可以使用字符串作为数组的索引 数组定义 普通数组定义: [rootnewrain shell]# books( linux shell awk sed ) 引用: [rootnewrain shell]# echo ${books[0]} linux [rootnewrain shell]# echo ${books[1]…

Kafka入门到实战-第四弹

Kafka入门到实战 Kafka集群搭建官网地址Kafka概述使用Kraft搭建Kafka集群更新计划 Kafka集群搭建 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://kafka.apache.org/Kafka概述 Apache Kafka 是一个开源的分布式事件…

数据库:Redis数据库

一、非关系型数据库 1.什么是非关系型数据库 非关系型数据库(Non-relational Database)又称NoSQL数据库是一种不同于传统关系型数据库管理系统(RDBMS)的数据存储解决方案。NoSQL这个术语最初意味着"Not Only SQL"&…

NoSQL(非关系型数据库)之Redis的简介与安装

一、简介 1.1 关系型数据库与非关系型数据库 1.1.1 概念 1.1.2 区别 1.2 非关系型数据库产生背景 1.3 redis 简介 1.4 redis 优点 1.5 redis 快的原因 二、安装 2.1 关闭核心防护 2.2 安装相关依赖 2.3 解压软件包并进行编译安装 2.4 设置 Redis 服务所需相关配置文…

代码随想录第28天 | 93.复原IP地址 、 78.子集 、 90.子集II

一、前言: 参考文献:代码随想录 今天的主题内容是回溯算法,这一章的干货很多,我需要慢慢的品味,不单单只是表象,还需要研究深层原理。 二、复原IP地址 1、思路: (1)…

HarmonyOS 应用开发之同步任务开发指导 (TaskPool和Worker)

同步任务是指在多个线程之间协调执行的任务,其目的是确保多个任务按照一定的顺序和规则执行,例如使用锁来防止数据竞争。 同步任务的实现需要考虑多个线程之间的协作和同步,以确保数据的正确性和程序的正确执行。 由于TaskPool偏向于单个独…

晚间兼职攻略:六个副业轻松上手

晚上兼职副业,作为增加额外收入的途径,选择多样且灵活。以下是六个特别适合晚上进行的副业,让你在闲暇时光也能充实自我,获得收益。 1,网络调查与市场研究是一个值得考虑的选项。你可以在晚上抽出空闲时间&#xff0c…

DEM高程数字模型制作技术分享

1. 引言 ​数字高程模型(Digital Elevation Model,简称DEM)是地形表面地形特征的数字表示。它提供了关于地面起伏、地形形态、地表特征等重要信息。在地理信息系统(GIS)、遥感、地质学、水利工程等领域,DEM…

群晖NAS使用Docker部署大语言模型Llama 2结合内网穿透实现公网访问本地GPT聊天服务

文章目录 1. 拉取相关的Docker镜像2. 运行Ollama 镜像3. 运行Chatbot Ollama镜像4. 本地访问5. 群晖安装Cpolar6. 配置公网地址7. 公网访问8. 固定公网地址 随着ChatGPT 和open Sora 的热度剧增,大语言模型时代,开启了AI新篇章,大语言模型的应用非常广泛,包括聊天机…

《信息技术服务 智能运维 第2部分:数据治理》国家标准2024年第一次线下编写会议成功召开

2024年3月13日~15日,由运维数据治理国标编制组主办的运维数据治理国家标准2024年第一次编写工作会议在上海成功召开。 本次会议由云智慧(北京)科技有限公司承办,来自南网数字集团信通公司、太保科技、平安银行、广发银行、广东农…

【电源专题】电池不均衡的影响与原因

在使用多节电池设计产品时,大家都知道如果多节电池不均衡会影响电池寿命与充电安全。特别是在充电末端与放电末端时表现较为明显。 电池不均衡的影响 那么为什么会影响安全与寿命呢?其原因如下: 如果电池不均衡时,相当于木桶的短板效应。一方面没法充满,充电时电压高的那一…

透明天气超实用工具更便捷地查看本地天气情况!

确切的气象数据播报,支持分钟级的降雨预测,精选的数百万张美丽城市背景图片和精美的风景图片,满足您与数百万朋友分享美丽天气的需求,用户友好的设计,简洁的界面布局,轻松查询天气信息的同时,还…

【论文笔记】Text2QR

论文:Text2QR: Harmonizing Aesthetic Customization and Scanning Robustness for Text-Guided QR Code Generation Abstract 二维码通常包含很多信息但看起来并不美观。stable diffusion的出现让平衡扫描鲁棒性和美观变为可能。 为了保证美观二维码的稳定生成&a…

06 | Swoole 源码分析之 Coroutine 协程模块

首发原文链接:Swoole 源码分析之 Coroutine 协程模块 大家好,我是码农先森。 引言 协程又称轻量级线程,但与线程不同的是;协程是用户级线程,不需要操作系统参与。由用户显式控制,可以在需要的时候挂起、或…

分享一种快速移植OpenHarmony Linux内核的方法

移植概述 本文面向希望将 OpenHarmony 移植到三方芯片平台硬件的开发者,介绍一种借助三方芯片平台自带 Linux 内核的现有能力,快速移植 OpenHarmony 到三方芯片平台的方法。 移植到三方芯片平台的整体思路 内核态层和用户态层 为了更好的解释整个内核…

曲线降采样之道格拉斯-普克算法Douglas–Peucker

曲线降采样之道格拉斯-普克算法Douglas–Peucker 该算法的目的是,给定一条由线段构成的曲线,找到一条点数较少的相似曲线,来近似描述原始的曲线,达到降低时间、空间复杂度和平滑曲线的目的。 附赠自动驾驶学习资料和量产经验&…

通过提交容器的方式修改ubuntu镜像的apt源

通过提交容器的方式修改ubuntu镜像的apt源 步骤总结 问题,每次创建容器之后,都要在容器内手动更改镜像源。 不如,干脆修改镜像的apt源,一次到位。 步骤 先创建一个容器,到容器内执行变更命令。 D:/sandbox> dock…

【Vue】vue3简介与环境配置

文章目录 项目编码规范什么是 Vue?安装node环境nvm针对node版本惊醒管理的工具 项目编码规范 组合式API Typescript setup(语法糖) 什么是 Vue? Vue 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建,…