当前位置: 首页 > 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 …...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; 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推流❌ 付费方案 &#xff08;部分有免费额度&#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出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...