第二讲 数据结构 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 …...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...