当前位置: 首页 > news >正文

第二讲 数据结构 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. 双链表

目录 双链表代码 && 思路 双链表 实现一个双链表&#xff0c;双链表初始为空&#xff0c;支持 5 种操作&#xff1a; 在最左侧插入一个数&#xff1b; 在最右侧插入一个数&#xff1b; 将第 k个插入的数删除&#xff1b; 在第 k 个插入的数左侧插入一个数&#xff1b…...

假期作业 2月6号

一、填空题 1、一个类的头文件如下所示&#xff0c;num初始化值为5&#xff0c;程序产生对象T&#xff0c;且修改num为10&#xff0c;并使用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 是一款基于&#xff08;wu-framework-parent&#xff09;孵化出的项目&#xff0c;内部使用Lazy ORM操作数据库&#xff0c;主要功能是网络穿透&#xff0c;对于没有公网IP的服务进行公网IP映射 使用环境JDK17 Spring Boot 3.0.2 功能 1.内网…...

【C++】C++入门(二)

个人主页 &#xff1a; zxctsclrjjjcph 文章封面来自&#xff1a;艺术家–贤海林 如有转载请先通知 文章目录 1. 前言2. 缺省参数2.1 缺省参数概念2.2 缺省参数分类 3. 函数重载3.1 函数重载概念3.2 C支持函数重载的原理--名字修饰(name Mangling) 1. 前言 在前面一篇文章中简…...

6.electron之上下文隔离,预加载JS脚本

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中&#xff0c;因此它允许你仅需一个代码仓库&#xff0c;就可以撰写支持 Windows、…...

【翻译】 Processing的安卓项目构建(译者用的是Android Studio)

原文链接&#xff1a;https://github.com/processing/processing-android/wiki/Building-Processing-for-Android&#xff0c;版本Apr 2, 2023 译者声明&#xff1a;这个文档是开源公开的&#xff0c;协议是GNU协议。译者自己得使用这个文档&#xff0c;所以才翻译的&#xff0…...

华为机考入门python3--(8)牛客8-合并表记录

分类&#xff1a;字典排序 知识点&#xff1a; 将输入转成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> 是一个内置组件&#xff0c;它的功能是在多个组件间动态切换时缓存被移除的组件实例。 基本使用 默认情况下&#xff0c;一个组件实例在被替换掉后会被销毁。这会导致它丢失其中所有已变化的状态——当这个组件再一次被显示时&#xff0c;会创建…...

RxJava Subject

目录 AsyncSubjectBehaviorSubjectPublishSubjectReplaySubjectSerializedSubjectUnicastSubject 在Rxjava中&#xff0c; Subject可以同时表示Observer和Observable, 允许从单个源到多个子观察者multiple child Observers。 除了 onSubscribe(io.reactivex.disposables.Dispos…...

[N-141]基于springboot,vue网上拍卖平台

开发工具&#xff1a;IDEA 服务器&#xff1a;Tomcat9.0&#xff0c; jdk1.8 项目构建&#xff1a;maven 数据库&#xff1a;mysql5.7 系统分前后台&#xff0c;项目采用前后端分离 前端技术&#xff1a;vueelementUI 服务端技术&#xff1a;springbootmybatis-plusredi…...

新能源光伏发电设计全面解析

伴随碳达峰、碳中和“双碳”政策大力推行&#xff0c;以及新能源市场的利好&#xff0c;目前多个城市在大力推进光伏发电项目&#xff0c;本篇文章将详细介绍关于光伏发电设计的信息。 一、光伏发电概念 光伏发电是指利用太阳辐射能在太阳能电池板上产生的电能&#xff0c;通…...

踩坑实录(Third Day)

临近年关&#xff0c;同事们该回家的也都回家了&#xff0c;所以我对工作的欲望不是很强烈&#xff0c;所以就主要是自己学习了一下&#xff0c;在 B 站看看视频&#xff0c;自己敲代码&#xff0c;所以今天没遇到什么坑&#xff0c;但是可以分享一下之前踩到的两个坑。 此为第…...

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&#xff0c;将默认的Form1重命名为FormPrinter&#xff0c;添加对 Newtonsoft.Json.dll用于读写Json字符串 zxing.dll&#xff0c;zxing.presentation.dll用于生成条形码&#xff0c;二维码…...

【PyQt】04-Designer

文章目录 前言一、初级 Designer1.1 拖拽设计界面1.2 搞定之后记得保存ui文件1.3 载入代码1.4 运行结果 二、登入界面代码效果展示账号密码错误时账号和密码正确 总结 前言 自然还是跟着王铭东老师学的 一、初级 Designer 1.1 拖拽设计界面 进度条是这个 1.2 搞定之后记得保…...

第4节、电机多段转动【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;本节介绍用控制步进电机三个主要参数角度、速度、方向&#xff0c;实现简单的步进电机多段控制 一、目标功能 输入多个目标角度&#xff0c;以及每个角度对应的速度&#xff0c;实现步进电机的多段多速…...

算法学习——华为机考题库1(HJ1 - HJ10)

算法学习——华为机考题库1&#xff08;HJ1 - HJ10&#xff09; HJ1 字符串最后一个单词的长度 描述 计算字符串最后一个单词的长度&#xff0c;单词以空格隔开&#xff0c;字符串长度小于5000。&#xff08;注&#xff1a;字符串末尾不以空格为结尾&#xff09; 输入描述&…...

PSQL常用操作

目录 前言 准备工作 添加postgres用户 初始化数据库 启动服务 创建数据库 psql连接数据库 常规操作 数据库 schema相关 插件 其他 前言 老折腾&#xff0c;还是记录点啥吧...... 基于本地PG数据库(打包为绿色版本了)&#xff0c;实操记录&#xff0c;版本pgsql12…...

C++ “万能血“ void*指针

本篇文章我们来介绍一下C “万能血” void指针 为什么说他万能呢&#xff1f; 原因:C void* 是一种特殊的指针类型&#xff0c;可用于存放任意对象的地址。在函数传参中也可以作为任何实参的形参 void型详细介绍 void* 是C中的一种特殊的指针类型&#xff0c;被称为"无类…...

微信小程序新手入门教程四:样式设计

WXSS (WeiXin Style Sheets)是一套样式语言&#xff0c;用于描述 WXML 的组件样式&#xff0c;决定了 WXML 的组件会怎么显示。 WXSS 具有 CSS 大部分特性&#xff0c;同时为了更适合开发微信小程序&#xff0c;WXSS 对 CSS 进行了扩充以及修改。与 CSS 相比&#xff0c;WXSS …...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...