【算法基础】链表
一、单链表

例题:
实现一个单链表,链表初始为空,支持三种操作:
向链表头插入一个数;
删除第 k个插入的数后面的数;
在第 k� 个插入的数后插入一个数。
现在要对该链表进行 M次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1个插入的数,第 2个插入的数,…第 n 个插入的数。
输入格式
第一行包含整数 M,表示操作次数。
接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:
H x,表示向链表头插入一个数 x。
D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。
I k x,表示在第 k 个插入的数后面插入一个数 x(此操作中 k 均大于 0)。
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6输出样例:
6 4 6 5代码:
#include <iostream>using namespace std;const int N =100010;//head:头结点的下标,
//e[i]表示结点i的值,
//ne[i]表示i的next指针
//idx存储当前已经用到的哪个点
int head, e[N], ne[N], idx;//初始化
void init()
{head = -1;idx = 0;}//将x插入到头结点
void add_to_head(int x)
{e[idx] = x;ne[idx] = head;head = idx;idx ++;
}//将x插入到下标是k的结点的后面
void add(int k, int x)
{e[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;
}//将下标是k的点后面的点删掉
void remove(int k)
{ne[k] = ne[ne[k]];}
int main()
{int m;cin >> m;init();while(m --){int k,x;char op;cin >> op;if(op == 'H'){cin >> x;add_to_head(x);}else if (op == 'D'){cin >> k;if(!k) head = ne[head];remove(k-1);}else {cin >> k >> x;add(k-1, x);}}for(int i = head; i!= -1; i = ne[i]) cout << e[i]<< " ";cout << endl;return 0;}二、双链表

例题:
实现一个双链表,双链表初始为空,支持 5 种操作:
在最左侧插入一个数;
在最右侧插入一个数;
将第 k 个插入的数删除;
在第 k 个插入的数左侧插入一个数;
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。
输入格式
第一行包含整数 M,表示操作次数。
接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:
L x,表示在链表的最左端插入数 x。
R x,表示在链表的最右端插入数 x。
D k,表示将第 k 个插入的数删除。
IL k x,表示在第 k 个插入的数左侧插入一个数。
IR k x,表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2输出样例:
8 7 7 3 2 9代码:
#include <iostream>using namespace std;const int N = 100010;int m;
int e[N], l[N], r[N], idx;//初始化
void init()
{// 0表示左端点点 1表示右端点r[0] = 1, l[1] = 0;idx = 2;}// 第k个插入的数右侧插入一个数
void add(int k, int x)
{e[idx] = x;r[idx] = r[k];l[idx] = k;l[r[k]] = idx;r[k] = idx;idx++;}//删除第k个点
void remove(int k)
{r[l[k]] = r[k];l[r[k]] = l[k];
}int main()
{init();cin >> m;while(m --){int k, x;string op;cin >> op;if(op == "L"){cin >> x;add(0, x);}else if(op == "R"){cin >> x;add(l[1], x);}else if(op == "D"){cin >> k;remove(k+1);}else if(op == "IL"){cin >> k >> x;add(l[k+1], x);}else {cin >> k >> x;add(k+1, x);}}for (int i=r[0]; i!= 1; i = r[i]) cout << e[i] << ' ';cout << endl;return 0;
}
相关文章:
【算法基础】链表
一、单链表例题:实现一个单链表,链表初始为空,支持三种操作:向链表头插入一个数;删除第 k个插入的数后面的数;在第 k� 个插入的数后插入一个数。现在要对该链表进行 M次操作,进行完所…...
[AUTOSAR][Fls模块] Flash Driver Module
Flash Driver Module--jianqiang.xue一、 简介二、 措施方式一:将FLASH操作程序作为Bootloader组件的一部分固化在存储器中方式二:通过通讯口将该部分代码从上位机下载到指定的RAM方式三:将Flash功能函数作为数据运行(推荐!&#…...
如何正确选择好用的投票平台微信公众平台投票链接链接投票平台
“年度人物楷模”网络评选投票_免费链接投票_作品投票通道_扫码投票怎样进行现在来说,公司、企业、学校更多的想借助短视频推广自己。通过微信投票小程序,网友们就可以通过手机拍视频上传视频参加活动,而短视频微信投票评选活动既可以给用户发…...
gocd部署应用
产品需要在多个环境部署测试,为了提高部署测试效率,故计划使用CD工具,jenkins确实足够强大,但是使用部署功能是需要安装插件的,再说自己本身只用部署功能,故决定找一个小巧的CD工具,经过一番查找…...
P2P视频聊天技术分析
整个P2P视频过程需要知道双方的媒体类型、流和候选者,所以这里就会用到一下技术: 信令服务器socket.io 状态机 ICE服务器 WebRTC框架 媒体协商 信令服务器Socket.io 信令服务器说白了作用就是发消息的中转站,A把msg发到…...
MyBatis 的一级、二级缓存机制
目录标题缓存什么是缓存为什么使用缓存什么样的数据能使用缓存,什么样的数据不能使用适用于缓存不适用于缓存MyBatis 一级缓存、二级缓存关系1. 一级缓存1.1 什么是一级缓存mybatis1.2 一级缓存配置1.3 什么情况下会命中一级缓存mybatis清除一级缓存的几种方法1.4 内…...
剑指 Offer 65. 不用加减乘除做加法
摘要 剑指 Offer 65. 不用加减乘除做加法 一、位运算 有符号整数通常用补码来表示和存储,补码具有如下特征: 正整数的补码与原码相同;负整数的补码为其原码除符号位外的所有位取反后加 11。可以将减法运算转化为补码的加法运算来实现。符…...
5年软件测试年薪30w+,我的坎坷之路谁又知道
在深圳做了五年软件测试工作,从之前的一脸懵的点点点,到现在会自动化测试,说一点点非计算机专业人员从事软件测试的心得体会,仅供参考交流。 大部分测试在公司没啥地位,当然如果你懂技术就还行,单纯点点点…...
【Opencv--自适应图像二值化】cv2.adaptiveThreshold()
【Opencv–adaptiveThreshold】自适应阈值图像二值化 文章目录【Opencv--adaptiveThreshold】自适应阈值图像二值化1. 介绍2. adaptiveThreshold函数2.1 函数调用2.2 补充说明3. 代码示例4. 效果4.1 原图(ori.img)4.2 处理后5. 参考1. 介绍 在这里 cv2.…...
洛谷P8601[蓝桥杯][2013年第四届真题]剪格子
题目描述如图 11 所示,33 的格子中填写了一些整数。我们沿着图中的红色线剪开,得到两个部分,每个部分的数字和都是 60。本题的要求就是请你编程判定:对给定的 mn 的格子中的整数,是否可以分割为两个部分,使…...
配置alias实现快速生成.gitignore文件
git工具:版本控制开发工具。 cscope工具:用于浏览C源码的工具,类似于ctags。在代码根目录下执行cscope -Rbq,然后产生三个索引文件(cscope.out、cscope.in.out和cscope.po.out三个文件)。 在Linux下使用vi…...
MySQL数据库调优————GROUP BY及DISTINCT优化
GROUP BY 三种处理GROUP BY的方式 松散索引扫描(Loose Index Scan)紧凑索引扫描(Tight Index Scan)临时表(Temporary table) 三种方式的性能一次递减 松散索引扫描 无需扫描满足条件的所有索引键即可返…...
LRU缓存算法
双向链表哈希表(非线程安全) https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/ /*** LRU算法: 哈希表双向链表实现* 1. 双向链表按照被使用的顺序来存储, 靠近头部的节点是最近使用的, 靠近尾部的节…...
@Configuration注解
Configuration注解介绍 Configuration注解,用于标注一个类是一个spring的配置类(同时,也是一个bean),配置类中可以使用ComponentScan、Import、ImportResource 和 Bean等注解的方式定义beanDefinition。 Target(Elem…...
基于springboot+vue的食疗系统
基于springbootvue的食疗系统 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目背景介绍&…...
sklearn学习-朴素贝叶斯
文章目录一、概述1、真正的概率分类器2、sklearn中的朴素贝叶斯二、不同分布下的贝叶斯1、高斯朴素贝叶斯GaussianNB2、探索贝叶斯:高斯朴素贝叶斯擅长的数据集3、探索贝叶斯:高斯朴素贝叶斯的拟合效果与运算速度总结一、概述 1、真正的概率分类器 算法…...
分享112个HTML艺术时尚模板,总有一款适合您
分享112个HTML艺术时尚模板,总有一款适合您 112个HTML艺术时尚模板下载链接:https://pan.baidu.com/s/1D3-mfPOud-f3vy9yLl-bmw?pwdfph2 提取码:fph2 Python采集代码下载链接:采集代码.zip - 蓝奏云 时尚平面模特网站模板 潮…...
用GDB远程调试运行于QEMU的程序
1. 前言 限于作者能力水平,本文可能存在谬误,因此而给读者带来的损失,作者不做任何承诺。 2. 测试环境 本文使用 Ubuntu 16.04.4 LTS QEMU 环境进行调试。 3. 用 GDB 调试 QEMU 内程序 3.1 编写用来调试的程序 我们用 ARM32 来进行调试…...
20 堆排序
文章目录1 堆排序的概念2 堆排序基本思想3 堆排序步骤图解说明4 堆排序的代码实现1 堆排序的概念 1) 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为 O(nlogn)…...
2023最新文件快递柜系统网站源码 | 匿名口令分享 | 临时文件分享
内容目录一、详细介绍二、效果展示1.部分代码2.效果图展示三、学习资料下载一、详细介绍 2023最新文件快递柜系统网站源码 | 匿名口令分享 | 临时文件分享 很多时候,我们都想将一些文件或文本传送给别人,或者跨端传递一些信息,但是我们又不…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
LangChain【6】之输出解析器:结构化LLM响应的关键工具
文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器?1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...
02-性能方案设计
需求分析与测试设计 根据具体的性能测试需求,确定测试类型,以及压测的模块(web/mysql/redis/系统整体)前期要与相关人员充分沟通,初步确定压测方案及具体的性能指标QA完成性能测试设计后,需产出测试方案文档发送邮件到项目组&…...
以太网PHY布局布线指南
1. 简介 对于以太网布局布线遵循以下准则很重要,因为这将有助于减少信号发射,最大程度地减少噪声,确保器件作用,最大程度地减少泄漏并提高信号质量。 2. PHY设计准则 2.1 DRC错误检查 首先检查DRC规则是否设置正确,然…...
IP选择注意事项
IP选择注意事项 MTP、FTP、EFUSE、EMEMORY选择时,需要考虑以下参数,然后确定后选择IP。 容量工作电压范围温度范围擦除、烧写速度/耗时读取所有bit的时间待机功耗擦写、烧写功耗面积所需要的mask layer...
