第二讲 数据结构 AcWing 827. 双链表
目录
- 双链表
- 代码 && 思路
双链表
实现一个双链表,双链表初始为空,支持 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;// 在节点a的右边插入一个数x
void insert(int a, int x)
{e[idx] = x; //第idx的节点的值为xl[idx] = a, //第idx的节点左指针指向当前节点ar[idx] = r[a]; //第idx的节点右指针指向a指针的右指针l[r[a]] = idx, //a节点原右边节点的指针的左指针指向当前idx节点r[a] = idx ++ ; //a节点现在的右指针指向idx 并让idx +1
}// 删除节点a
void remove(int a)
{l[r[a]] = l[a]; //a节点右边节点的左指针指向a节点的左节点r[l[a]] = r[a]; //a节点的左节点的右指针指向a节点的右节点
}int main()
{cin >> m;// 0是左端点,1是右端点r[0] = 1, l[1] = 0; //这是两个哨兵节点idx = 2; //表示双链表里面初始有两个节点 其实就是哨兵节点 一个指向链表的头结点 一个指向链表的尾节点while (m -- ){string op;cin >> op;int k, x;if (op == "L"){cin >> x;insert(0, x);}else if (op == "R"){cin >> x;insert(l[1], x);}else if (op == "D"){cin >> k;remove(k + 1);}else if (op == "IL"){cin >> k >> x;insert(l[k + 1], x);}else{cin >> k >> x;insert(k + 1, x);}}for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';cout << endl;return 0;
}
相关文章:
第二讲 数据结构 AcWing 827. 双链表
目录 双链表代码 && 思路 双链表 实现一个双链表,双链表初始为空,支持 5 种操作: 在最左侧插入一个数; 在最右侧插入一个数; 将第 k个插入的数删除; 在第 k 个插入的数左侧插入一个数;…...
假期作业 2月6号
一、填空题 1、一个类的头文件如下所示,num初始化值为5,程序产生对象T,且修改num为10,并使用show()函数输出num的值10。 #include <iostream.h> class Test { private: static int num; public: Test(int); void show(); };…...
【wu-lazy-cloud-network】Java自动化内网穿透
项目介绍 wu-lazy-cloud-network 是一款基于(wu-framework-parent)孵化出的项目,内部使用Lazy ORM操作数据库,主要功能是网络穿透,对于没有公网IP的服务进行公网IP映射 使用环境JDK17 Spring Boot 3.0.2 功能 1.内网…...
【C++】C++入门(二)
个人主页 : zxctsclrjjjcph 文章封面来自:艺术家–贤海林 如有转载请先通知 文章目录 1. 前言2. 缺省参数2.1 缺省参数概念2.2 缺省参数分类 3. 函数重载3.1 函数重载概念3.2 C支持函数重载的原理--名字修饰(name Mangling) 1. 前言 在前面一篇文章中简…...
6.electron之上下文隔离,预加载JS脚本
如果可以实现记得点赞分享,谢谢老铁~ Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中,因此它允许你仅需一个代码仓库,就可以撰写支持 Windows、…...
【翻译】 Processing的安卓项目构建(译者用的是Android Studio)
原文链接:https://github.com/processing/processing-android/wiki/Building-Processing-for-Android,版本Apr 2, 2023 译者声明:这个文档是开源公开的,协议是GNU协议。译者自己得使用这个文档,所以才翻译的࿰…...
华为机考入门python3--(8)牛客8-合并表记录
分类:字典排序 知识点: 将输入转成int的列表 my_list list(map(int, input().strip().split( ))) 将列表转为元组 tuple(my_list) 访问元素为元组的列表 for first, second, third in my_list: 对字典进行排序 sorted(my_dict.items())…...
vue3-内置组件-KeepAlive
KeepAlive <KeepAlive> 是一个内置组件,它的功能是在多个组件间动态切换时缓存被移除的组件实例。 基本使用 默认情况下,一个组件实例在被替换掉后会被销毁。这会导致它丢失其中所有已变化的状态——当这个组件再一次被显示时,会创建…...
RxJava Subject
目录 AsyncSubjectBehaviorSubjectPublishSubjectReplaySubjectSerializedSubjectUnicastSubject 在Rxjava中, Subject可以同时表示Observer和Observable, 允许从单个源到多个子观察者multiple child Observers。 除了 onSubscribe(io.reactivex.disposables.Dispos…...
[N-141]基于springboot,vue网上拍卖平台
开发工具:IDEA 服务器:Tomcat9.0, jdk1.8 项目构建:maven 数据库:mysql5.7 系统分前后台,项目采用前后端分离 前端技术:vueelementUI 服务端技术:springbootmybatis-plusredi…...
新能源光伏发电设计全面解析
伴随碳达峰、碳中和“双碳”政策大力推行,以及新能源市场的利好,目前多个城市在大力推进光伏发电项目,本篇文章将详细介绍关于光伏发电设计的信息。 一、光伏发电概念 光伏发电是指利用太阳辐射能在太阳能电池板上产生的电能,通…...
踩坑实录(Third Day)
临近年关,同事们该回家的也都回家了,所以我对工作的欲望不是很强烈,所以就主要是自己学习了一下,在 B 站看看视频,自己敲代码,所以今天没遇到什么坑,但是可以分享一下之前踩到的两个坑。 此为第…...
Linux联网安装MySQL Server
yum安装 以下代码复制粘贴到控制台即可 yum list | grep mysql-server #查看可以下载的MySQLyum install -y mysql-server #安装MySQLmysql_secure_installation #引导安装 引导安装实例如下 systemctl enable mysqld 设置开机自动启动 systemctl sta…...
使用GDI画图片生成合成图片并调用打印机进行图片打印
使用GDI画图片生成合成图片并调用打印机进行图片打印 新建窗体应用程序PrinterDemo,将默认的Form1重命名为FormPrinter,添加对 Newtonsoft.Json.dll用于读写Json字符串 zxing.dll,zxing.presentation.dll用于生成条形码,二维码…...
【PyQt】04-Designer
文章目录 前言一、初级 Designer1.1 拖拽设计界面1.2 搞定之后记得保存ui文件1.3 载入代码1.4 运行结果 二、登入界面代码效果展示账号密码错误时账号和密码正确 总结 前言 自然还是跟着王铭东老师学的 一、初级 Designer 1.1 拖拽设计界面 进度条是这个 1.2 搞定之后记得保…...
第4节、电机多段转动【51单片机+L298N步进电机系列教程】
↑↑↑点击上方【目录】,查看本系列全部文章 摘要:本节介绍用控制步进电机三个主要参数角度、速度、方向,实现简单的步进电机多段控制 一、目标功能 输入多个目标角度,以及每个角度对应的速度,实现步进电机的多段多速…...
算法学习——华为机考题库1(HJ1 - HJ10)
算法学习——华为机考题库1(HJ1 - HJ10) HJ1 字符串最后一个单词的长度 描述 计算字符串最后一个单词的长度,单词以空格隔开,字符串长度小于5000。(注:字符串末尾不以空格为结尾) 输入描述&…...
PSQL常用操作
目录 前言 准备工作 添加postgres用户 初始化数据库 启动服务 创建数据库 psql连接数据库 常规操作 数据库 schema相关 插件 其他 前言 老折腾,还是记录点啥吧...... 基于本地PG数据库(打包为绿色版本了),实操记录,版本pgsql12…...
C++ “万能血“ void*指针
本篇文章我们来介绍一下C “万能血” void指针 为什么说他万能呢? 原因:C void* 是一种特殊的指针类型,可用于存放任意对象的地址。在函数传参中也可以作为任何实参的形参 void型详细介绍 void* 是C中的一种特殊的指针类型,被称为"无类…...
微信小程序新手入门教程四:样式设计
WXSS (WeiXin Style Sheets)是一套样式语言,用于描述 WXML 的组件样式,决定了 WXML 的组件会怎么显示。 WXSS 具有 CSS 大部分特性,同时为了更适合开发微信小程序,WXSS 对 CSS 进行了扩充以及修改。与 CSS 相比,WXSS …...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
