AcWing 827. 双链表——算法基础课题解

AcWing 827. 双链表

题目描述

实现一个双链表，双链表初始为空，支持 5 种操作：

  1. 在最左侧插入一个数；
  2. 在最右侧插入一个数；
  3. 将第 k 个插入的数删除；
  4. 在第 k 个插入的数左侧插入一个数；
  5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，……第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

  1. L x，表示在链表的最左端插入数 x。
  2. R x，表示在链表的最右端插入数 x。
  3. D k，表示将第 k 个插入的数删除。
  4. IL k x，表示在第 k 个插入的数左侧插入一个数。
  5. 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

C++

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int current, value[N], l[N], r[N];

void insert(int k, int x) {
    value[current] = x;
    l[current] = k, r[current] = r[k];
    l[r[k]] = current, r[k] = current++;
}

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main() {
    int m;
    scanf("%d", &m);
    r[0] = 1, l[1] = 0;
    current = 2;
    while (m--) {
        char command[3];
        int k, x;
        scanf("%s", command);
        if (command[0] == 'L') {
            scanf("%d", &x);
            insert(0, x);
        } else if (command[0] == 'R') {
            scanf("%d", &x);
            insert(l[1], x);
        } else if (command[0] == 'D') {
            scanf("%d", &k);
            remove(k + 1);
        } else if (command[1] == 'L') {
            scanf("%d%d", &k, &x);
            insert(l[k + 1], x);
        } else {
            scanf("%d%d", &k, &x);
            insert(k + 1, x);
        }

    }
    for (int i = r[0]; i != 1; i = r[i]) printf("%d ", value[i]);
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int current, value[N], l[N], r[N];

void insert(int k, int x) {
    value[current] = x;
    l[current] = k, r[current] = r[k];
    l[r[k]] = current, r[k] = current++;
}

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int m;
    cin >> m;
    r[0] = 1, l[1] = 0;
    current = 2;
    while (m--) {
        string command;
        int k, x;
        cin >> command;
        if (command[0] == 'L') {
            cin >> x;
            insert(0, x);
        } else if (command[0] == 'R') {
            cin >> x;
            insert(l[1], x);
        } else if (command[0] == 'D') {
            cin >> k;
            remove(k + 1);
        } else if (command[1] == 'L') {
            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 << value[i] << ' ';
    return 0;
}

#include <iostream>

using namespace std;

struct Node {
    int value;
    int left;
    int right;
};

const int N = 1e5 + 10;
Node nodes[N];
int current;

void insert(int k, int x) {
    nodes[current].value = x;
    nodes[current].left = k;
    nodes[current].right = nodes[k].right;
    nodes[nodes[k].right].left = current;
    nodes[k].right = current++;
}

void remove(int k) {
    nodes[nodes[k].left].right = nodes[k].right;
    nodes[nodes[k].right].left = nodes[k].left;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int m;
    cin >> m;
    nodes[0].right = 1;
    nodes[1].left = 0;
    current = 2;
    while (m--) {
        string command;
        int k, x;
        cin >> command;
        if (command[0] == 'L') {
            cin >> x;
            insert(0, x);
        } else if (command[0] == 'R') {
            cin >> x;
            insert(nodes[1].left, x);
        } else if (command[0] == 'D') {
            cin >> k;
            remove(k + 1);
        } else if (command[1] == 'L') {
            cin >> k >> x;
            insert(nodes[k + 1].left, x);
        } else {
            cin >> k >> x;
            insert(k + 1, x);
        }

    }
    for (int i = nodes[0].right; i != 1; i = nodes[i].right) cout << nodes[i].value << ' ';
    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const N = 1e5 + 10

var (
	current int
	value   [N]int
	l       [N]int
	r       [N]int
)

func insert(k, x int) {
	value[current] = x
	l[current] = k
	r[current] = r[k]
	l[r[k]] = current
	r[k] = current
	current++
}

func remove(k int) {
	r[l[k]] = r[k]
	l[r[k]] = l[k]
}

func main() {
	reader := bufio.NewScanner(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var m int
	fmt.Scanf("%d", &m)

	r[0] = 1
	l[1] = 0
	current = 2

	for i := 0; i < m; i++ {
		reader.Scan()
		line := reader.Text()
		parts := strings.Fields(line)
		command := parts[0]
		switch command {
		case "L":
			x, _ := strconv.Atoi(parts[1])
			insert(0, x)
		case "R":
			x, _ := strconv.Atoi(parts[1])
			insert(l[1], x)
		case "D":
			k, _ := strconv.Atoi(parts[1])
			remove(k + 1)
		case "IL":
			k, _ := strconv.Atoi(parts[1])
			x, _ := strconv.Atoi(parts[2])
			insert(l[k+1], x)
		case "IR":
			k, _ := strconv.Atoi(parts[1])
			x, _ := strconv.Atoi(parts[2])
			insert(k+1, x)
		}
	}

	for i := r[0]; i != 1; i = r[i] {
		fmt.Fprintf(writer, "%d ", value[i])
	}
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Node struct {
	value int
	left  int
	right int
}

const N = 1e5 + 10

var (
	nodes   [N]Node
	current int
)

func insert(k, x int) {
	nodes[current].value = x
	nodes[current].left = k
	nodes[current].right = nodes[k].right
	nodes[nodes[k].right].left = current
	nodes[k].right = current
	current++
}

func remove(k int) {
	nodes[nodes[k].left].right = nodes[k].right
	nodes[nodes[k].right].left = nodes[k].left
}

func main() {
	reader := bufio.NewScanner(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var m int
	fmt.Scanf("%d", &m)

	nodes[0].right = 1
	nodes[1].left = 0
	current = 2

	for i := 0; i < m; i++ {
		reader.Scan()
		line := reader.Text()
		parts := strings.Fields(line)
		switch parts[0] {
		case "L":
			x, _ := strconv.Atoi(parts[1])
			insert(0, x)
		case "R":
			x, _ := strconv.Atoi(parts[1])
			insert(nodes[1].left, x)
		case "D":
			k, _ := strconv.Atoi(parts[1])
			remove(k + 1)
		case "IL":
			k, _ := strconv.Atoi(parts[1])
			x, _ := strconv.Atoi(parts[2])
			insert(nodes[k+1].left, x)
		case "IR":
			k, _ := strconv.Atoi(parts[1])
			x, _ := strconv.Atoi(parts[2])
			insert(k+1, x)
		}
	}

	for i := nodes[0].right; i != 1; i = nodes[i].right {
		fmt.Fprintf(writer, "%d ", nodes[i].value)
	}
}

模板

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/597818.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

STM32CubeMX学习笔记32---FreeRTOS资源管理

STM32CubeMX学习笔记32---FreeRTOS资源管理

一、CPU利用率简介 1 基本概念 CPU 使用率其实就是系统运行的程序占用的 CPU 资源&#xff0c;表示机器在某段时间程序运行的情况&#xff0c;如果这段时间中&#xff0c;程序一直在占用 CPU 的使用权&#xff0c;那么可以人为 CPU 的利用率是 100%。CPU 的利用率越高&#xf…
阅读更多...
JVM调参实践总结

JVM调参实践总结

JVM调优–理论篇从理论层面介绍了如何对JVM调优。这里再写一篇WIKI&#xff0c;尝试记录下JVM参数使用的最佳实践&#xff0c;注意&#xff0c;这里重点介绍HotSpot VM的调参&#xff0c;其他JVM的调参可以类比&#xff0c;但不可照搬。 Java版本选择 基于Java开发应用时&…
阅读更多...
面向新手在无人机竞速场景下的飞行辅助系统——浙大 FAST-Lab 高飞团队 ICRA 论文三项 Best Paper 入围

面向新手在无人机竞速场景下的飞行辅助系统——浙大 FAST-Lab 高飞团队 ICRA 论文三项 Best Paper 入围

恭喜浙江大学 FAST-Lab 钟宇航同学的论文 A Trajectory-based Flight Assistive System for Novice Pilots in Drone Racing Scenario 顺利发表 ICRA 2024&#xff0c;并同时入选三项 Finalist&#xff1a; the IEEE ICRA Best Conference Paper Awardthe IEEE ICRA Best Pape…
阅读更多...
干货！Kali Linux命令大全（建议收藏）

干货！Kali Linux命令大全（建议收藏）

系统信息 arch 显示机器的处理器架构 name -m 显示机器的处理器架构 name -r 显示正在使用的内核版本 dmidecode -q 显示硬件系统部件 -(SMBIOS/DMI) hdparm -i /dev/hda 罗列一个磁盘的架构特性 hdparm -tT /dev/sda 在磁盘上执行测试读取操作 cat /proc/cpuinfo …
阅读更多...
[综合应用]dns nfs httpd php mysql

[综合应用]dns nfs httpd php mysql

第一步&#xff1a;搭建三台主机 主机名称 Ip地址 角色 503A 192.168.68.10 Mysql从 503B 192.168.68.11 Mysql从&#xff0c;nfs服务端&#xff0c;dns服务端 503Cmysql 192.168.68.12 MySQL主&#xff0c;web客户端 第二步&#xff1a;在503B上配置DNS 2.1 下载…
阅读更多...
【3dmax笔记】027：配置修改器集、工具栏自定义与加载

【3dmax笔记】027：配置修改器集、工具栏自定义与加载

文章目录 一、配置修改器集二、自定义工具栏三、加载工具栏 一、配置修改器集 可以把自己常用的修改命令放到右边框中的部分&#xff0c;便于自己的操作&#xff0c;省去了每次都要花半天时间找命令的尴尬。新建一个二维或者三维物体&#xff0c;点击修改面板&#xff0c;点击…
阅读更多...
三分钟了解计算机网络核心概念-数据链路层和物理层

三分钟了解计算机网络核心概念-数据链路层和物理层

计算机网络数据链路层和物理层 节点&#xff1a;一般指链路层协议中的设备。 链路&#xff1a;一般把沿着通信路径连接相邻节点的通信信道称为链路。 MAC 协议&#xff1a;媒体访问控制协议&#xff0c;它规定了帧在链路上传输的规则。 奇偶校验位&#xff1a;一种差错检测方…
阅读更多...
【含win+Mac整合包】本地部署Stable Diffusion，超详细（AI 绘画保姆级教程，100%成功部署）

【含win+Mac整合包】本地部署Stable Diffusion，超详细（AI 绘画保姆级教程，100%成功部署）

什么是stable diffusion? stable diffusion是在2022年发布的基于扩散模型的文本到图像生成模型&#xff0c;起初它只有一堆api供开发者使用&#xff0c;可以说非常难上手&#xff0c;随着2023年5月由AUTOMATIC1111大佬基于SD API开发的SD WebUI的发布&#xff0c;SD第一次有了…
阅读更多...
C++进阶之路：何为引用、内联函数、auto与指针空值nullptr关键字

C++进阶之路：何为引用、内联函数、auto与指针空值nullptr关键字

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…
阅读更多...
【运维自动化-配置平台】如何对主机进行纳管

【运维自动化-配置平台】如何对主机进行纳管

主机是配置平台管控最常见的资源&#xff0c;也是运维日常主要的管控对象&#xff1b;如何对主机进行全生命周期管理呢导入主机 直接导入 直接导入仅适用于直连区域&#xff08;default area&#xff09;的主机&#xff0c;也就是网络跟蓝鲸平台能内网互通的。 资源–>主…
阅读更多...
西奥机电食品质构分析仪：揭秘水果蔬菜硬度等指标的测试原理

西奥机电食品质构分析仪：揭秘水果蔬菜硬度等指标的测试原理

西奥机电食品质构分析仪&#xff1a;揭秘水果蔬菜硬度等指标的测试原理 在食品科学领域&#xff0c;对水果蔬菜硬度的精准测量是评估其品质与口感的重要步骤。西奥机电食品质构分析仪凭借其先进的技术和独特的测试原理&#xff0c;为这一领域带来了革命性的变革。下面&#xf…
阅读更多...
非标类型导致Dubbo接口出入参异常的本质 ｜ 得物技术

非标类型导致Dubbo接口出入参异常的本质 ｜ 得物技术

一、概述 笔者支持过程中多次发现诡异的Dubbo接口异常问题&#xff0c;抓耳挠腮最后定位到代码上和代码外的原因&#xff0c;事后只感觉脑瓜子嗡嗡的。考虑到这不是第一次&#xff0c;也绝不会是最后一次出现类似问题&#xff0c;下面笔者将尽可能详细的梳理、总结一下该问题的…
阅读更多...
6个月小猫成长必备！福派斯无麸质幼猫粮评测

6个月小猫成长必备！福派斯无麸质幼猫粮评测

你知道吗&#xff1f;给小猫选择适合的猫粮是一件非常不容易但很重要的事情。那么&#xff0c;对于6个月大的小猫来说&#xff0c;什么样的猫粮是最适合它们的呢&#xff1f;&#x1f431; 我们首先要考虑的是猫粮的营养成分。6个月大的小猫正处于快速生长期&#xff0c;所以需…
阅读更多...
vue3 + ts实现canvas绘制的waterfall

vue3 + ts实现canvas绘制的waterfall

实际运行效果（仅包含waterfall图表部分） component.vue <template><div ref="heatmap" :style="{ height: props.containerHeight + px }" /> </template><script setup> import ColorMap from "colormap"; import…
阅读更多...
Labels and Databases for Mac：强大的标签与数据库管理工具

Labels and Databases for Mac：强大的标签与数据库管理工具

Labels and Databases for Mac是一款集标签制作与数据库管理于一体的强大工具&#xff0c;专为Mac用户打造&#xff0c;旨在提供高效、便捷的标签制作与数据管理体验。 这款软件拥有丰富的内置标签格式&#xff0c;用户可轻松创建各种标签、信封和卡片&#xff0c;满足个性化需…
阅读更多...
掌控网络流量,优化网络性能 - AnaTraf网络流量分析仪登场

掌控网络流量,优化网络性能 - AnaTraf网络流量分析仪登场

在当今日新月异的网络环境中,网络流量监控和性能诊断已成为企业IT部门不可或缺的重要工作。只有充分了解网络流量状况,才能有效优化网络性能,提高业务运营效率。针对这一需求,全新推出的AnaTraf网络流量分析仪应运而生,为企业提供全面的网络监控和性能诊断解决方案。 快速定位…
阅读更多...
Java双亲委派机制

Java双亲委派机制

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 概述 Java程序在运…
阅读更多...
pygame实现鼠标绘制并调节画笔大小

pygame实现鼠标绘制并调节画笔大小

pygame实现鼠标绘制并调节画笔大小 pygame介绍调节画笔大小鼠标绘制效果 pygame介绍 Pygame是一个开源的Python库&#xff0c;专为电子游戏开发而设计。它建立在SDL&#xff08;Simple DirectMedia Layer&#xff09;的基础上&#xff0c;允许开发者使用Python这种高级语言来实…
阅读更多...
C语言趣味代码（五）

C语言趣味代码（五）

我想以此篇结束关于C语言的博客&#xff0c;因为在C语言拖得越久越不能给大家带来新的创作&#xff0c;在此我也相信大家对C语言已经有了一个新的认知。进入正题&#xff0c;在这一篇中我主要编一个“英语单词练习小程序”来给大家展开介绍&#xff0c;从测试版逐步改良&#x…
阅读更多...
数据结构——图的基础知识与其表示

数据结构——图的基础知识与其表示

一&#xff1a;定义 由顶点的集合和边的集合组成&#xff1b;常以 G(V,E) 表示&#xff0c;G 代表图&#xff0c;V代表 顶点的集合&#xff0c;E代表边的集合&#xff1b; 如图&#xff1a; 在G1图中&#xff0c;有 0~4 五个顶点&#xff0c;有 0-1&#xff0c;0-2&…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站