第二讲 数据结构 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 …...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...

视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...