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

B3631 单向链表-模拟链表

来源 :题目链接-洛谷

B3631 单向链表

单向链表

题目描述

实现一个数据结构,维护一张表(最初只有一个元素 1 1 1)。需要支持下面的操作,其中 x x x y y y 都是 1 1 1 1 0 6 10^6 106 范围内的正整数,且保证任何时间表中所有数字均不相同,操作数量不多于 1 0 5 10^5 105

  • 1 x y :将元素 y y y 插入到 x x x 后面;
  • 2 x :询问 x x x 后面的元素是什么。如果 x x x 是最后一个元素,则输出 0 0 0
  • 3 x:从表中删除元素 x x x 后面的那个元素,不改变其他元素的先后顺序。

输入格式

第一行一个整数 q q q 表示操作次数。

接下来 q q q 行,每行表示一次操作,操作具体间题目描述。

输出格式

对于每个操作 2,输出一个数字,用换行隔开。

样例 #1

样例输入 #1

6
1 1 99
1 99 50
1 99 75
2 99
3 75
2 1

样例输出 #1

75
99

题意

值x和值y进行一系列在链表中插入、删除节点、查找节点的操作(没有给出数据位置,所以常规的下标处理数据会不正确)

思路

思考: 如何根据值能够快速的插入/查找数据的位置??
(链表能快速删除和插入,但是需要知道具体位置,需要遍历
(常规的vector能快速查找,但是删除和插入需要耗费很多时间)

STL中链表的局限性:

  1. 迭代器访问速度:虽然 在操作上有良好的时间复杂度,但它并不具备随机访问特性。 每次访问某个特定元素时,都需要从头或尾遍历链表到该位置,这会导致性能问题。list
  2. 内存分配: 会频繁进行内存分配和释放,尤其是在链表的大小较大时,这可能导致额外的内存管理开销。list

因此,如果题目要求进行频繁的随机访问或查找,STL的可能会超时。list

  • 在C++中,list是一个双向链表实现,提供了常数时间复杂度(O(1))的插入和删除操作,但它仍然会在一些特定情况下导致超时。比如:查找,查找只能是从头开始遍历,当链表比较长,如果操作大多都是查找且链表比较长,那就G了。这个题就是最后,两个点会超时。所以必须模拟链表优化处理

  • 手动实现一个链表结构,模拟它的操作。 通过手动管理内存和节点的连接。考虑到数据不会重复,所以直接考虑所有数据存在对于的下标中,这样遍历可以像数组一样方便处理,遍历时间最小化。结构体储存值和下一个节点的下标(其实值都可以省略,偷懒直接用数组也行,反正值=下标)

  • 因为数据长度不大,在删除时,用空间换时间,就不用真的删除节点,而是直接改后继节点(下一个节点的下标)的数据就行

数据约束

  • 链表的数据 n≤10^6。
  • 操作数(m),m≤10^5。
  • 操作的类型删除或查找节点如果常规操作容易超时。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
//数据最好是有用结构体储存值+位置信息(一幕操作给出的不是位置,是数据值) 
struct node{int v;int ne;
}s[N];
int len = 1; 
void insert(int x,int y);
void del(int x); 
int main()
{//初始化数据s[1].v = 1,s[1].ne = -1; int q,k,x,y;cin>>q;while(q--){cin>>k;if(k==1){cin>>x>>y;insert(x, y);  }else if(k==2){cin>>x;if(s[x].ne==-1){ //判断的标准不是长度为1 而是确定后继节点!!! 最后一个元素不等于只有一个元素 cout<<0<<endl;}else{//遍历数据 int res = s[x].ne;cout<<res<<endl;//直接找到x指向的下一个数的位置,就不用从前往后遍历 }}else{cin>>x;//删除 del(x) ;}}return 0;
}
void insert(int x,int y){ //模拟单项链表的插入 s[y].v =y;//插入一个数据s[y].ne = s[x].ne;//储存x之前后面的位置 s[x].ne = y;//插入数据搭配x后面 len++;
}
void del(int x){s[x].ne = s[s[x].ne].ne;//直接改指针的方向 //空间换时间,直接改变指针就行 len--; 
} 

相关文章:

B3631 单向链表-模拟链表

来源 &#xff1a;题目链接-洛谷 B3631 单向链表 单向链表 题目描述 实现一个数据结构&#xff0c;维护一张表&#xff08;最初只有一个元素 1 1 1&#xff09;。需要支持下面的操作&#xff0c;其中 x x x 和 y y y 都是 1 1 1 到 1 0 6 10^6 106 范围内的正整数&…...

【C++】格式化输出详解:掌握 cout 的进阶用法

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;格式化输出的理论概述&#x1f4af;控制输出宽度和填充字符setw 操作符setfill 操作符 &#x1f4af;控制浮点数的显示格式fixed 与 scientificsetprecision &#x1f4af;…...

【NoSQL数据库】Hbase基本操作——数据库表的增删改查

目录 一、Hbase原理 二、HBase数据库操作 三、遇到的问题和解决方法 一、Hbase原理 HBase的数据模型&#xff1a; 行键 时间戳 列族&#xff1a;contents 列族&#xff1a;anchor 列族&#xff1a;mime “com.cnn.www” T9 Achor:cnnsi.com”CNN” T8 Achor:…...

同步fifo

同步FIFO FIFO即是一种先进先出的数据缓存器。同步FIFO指的是数据的写入和读出的时钟是同一个时钟。异步 FIFO 有两个时钟信号&#xff0c;读和写逻辑用的各自的读写时钟。 FIFO没有外部读写地址线&#xff0c;使用起来简单。但是缺点就是只能先入先出&#xff0c;数据地址由…...

肌肉骨骼肿瘤治疗市场:潜力无限,未来可期

肌肉骨骼肿瘤治疗作为现代医学的重要分支&#xff0c;专注于应对骨骼和肌肉系统中的良性和恶性肿瘤。随着全球人口老龄化和生活方式的改变&#xff0c;肌肉骨骼疾病日益成为公共卫生的重要问题。与此同时&#xff0c;医疗技术的进步和患者对高质量医疗服务的需求不断推动该市场…...

高考倒计时:用倒计时软件 为梦想加油 可用于教室黑板或者电脑上

高考&#xff0c;这个被无数学子视为人生重要转折点的考试&#xff0c;即将来临。每一年的六月&#xff0c;都充满了紧张与期待。如何在这场人生的战役中取得胜利&#xff1f;除了日常的勤奋学习&#xff0c;科学的复习计划和心态调整外&#xff0c;一款好用的倒计时软件&#…...

人工智能学习用的电脑安装cuda、torch、conda等软件,版本的选择以及多版本切换

接触人工智能的学习三个月了&#xff0c;每天与各种安装包作斗争&#xff0c;缺少依赖包、版本高了、版本低了、不兼容了、系统做一半从头再来了。。。这些都是常态。三个月把单位几台电脑折腾了不下几十次安装&#xff0c;是时候总结一下踩过的坑和积累的经验了。 以一个典型的…...

BERT模型的输出格式探究以及提取出BERT 模型的CLS表示,last_hidden_state[:, 0, :]用于提取每个句子的CLS向量表示

说在前面 最近使用自己的数据集对bert-base-uncased进行了二次预训练&#xff0c;只使用了MLM任务&#xff0c;发现在加载训练好的模型进行输出CLS表示用于下游任务时&#xff0c;同一个句子的输出CLS表示都不一样&#xff0c;并且控制台输出以下警告信息。说是没有这些权重。…...

InfluxDB 集成 Grafana

将InfluxDB集成到Grafana进行详细配置通常包括以下几个步骤&#xff1a;安装与配置InfluxDB、安装与配置Grafana、在Grafana中添加InfluxDB数据源以及创建和配置仪表板。以下是一个详细的配置指南&#xff1a; 一、安装与配置InfluxDB 下载与安装&#xff1a; 从InfluxDB的官…...

Vue跨标签通讯(本地存储)(踩坑)

我司有一个需求【用户指引】 需求是根标签有一个用户指引总开关&#xff0c;可以控制页面所有的用户指引是否在页面进入后初始是否默认打开&#xff0c;但是有些页面会新开标签这就设计到跨标签通讯了 我采取的方案是本地存储 重点:首先本地存储在页面是同源(即域名协议端口三…...

掌握创意之钥:全面解析HTML5 Canvas

在数字时代&#xff0c;表达创意的方式多种多样&#xff0c;而 HTML5 中的 <canvas> 元素无疑为网页开发者提供了一个强大的工具箱。无论你是想要创建动态图表、互动游戏还是复杂的可视化应用&#xff0c;掌握 Canvas 的基本用法都是迈向成功的关键一步。本文将带你一步步…...

mac port 安装redis 并设置为系统服务 自定义配置方法

mac系统中&#xff0c;port 包管理工具比brew的速度快N倍&#xff0c;今天就给大家分享一下在macos系统中如何使用 port安装 redis数据库并配置为服务自动启动和自定义redis.conf配置的方法。 1. 安装redis sudo port install redis 2. 启动redis服务 sudo port load redis …...

Agent AI: Surveying the Horizons of Multimodal Interaction---摘要、引言、代理 AI 集成

题目 智能体AI:多模态交互视野的考察 论文地址&#xff1a;https://arxiv.org/abs/2401.03568 图1&#xff1a;可以在不同领域和应用程序中感知和行动的Agent AI系统概述。Agent AI是正在成为通用人工智能&#xff08;AGI&#xff09;的一个有前途的途径。Agent AI培训已经证…...

二百七十八、ClickHouse——将本月第一天所在的那一周视为第一周,无论它是从周几开始的,查询某个日期是本月第几周

一、目的 ClickHouse指标表中有个字段week_of_month&#xff0c;含义是这条数据属于本月第几周。 而且将本月第一天所在的那一周视为第一周&#xff0c;无论它是从周几开始的。比如2024-12-01是周日&#xff0c;即12月第一周。而2024-12-02是周一&#xff0c;即12月第二周 二…...

Unity 相机旋转及角度限制

前言 由于欧拉角具有直观的可读性&#xff0c;做相机旋转时选择修改eulerAngles 来实现旋转&#xff0c;但实际效果与预期稍有不同&#xff0c;这是因为欧拉角受到万向锁&#xff08;Gimbal Lock&#xff09;的影响&#xff0c;在赋值时需要对输入的角度进行调整。 if (value…...

基于CentOS系统利用Kamailio搭建企业级SIP服务器

一、Kamailio简介 Kamailio是一款开源的SIP服务器&#xff0c;具有高性能、可扩展、模块化等特点。它广泛应用于VoIP、即时通讯、视频会议等领域。Kamailio支持多种操作系统&#xff0c;如Linux、FreeBSD等&#xff0c;可以与其他开源项目&#xff08;如 Asterisk、FreeSWITCH…...

部署项目报错

vue2项目部署后 Error: Cannot find module /views/*** 1.起因 登录页、首页等静态页面可以正常进入&#xff0c;后端访问也正常&#xff0c;可以获取到验证码。 但是登录之后会发现首页空白或者进入不到首页 F12查看有报错信息&#xff1a;Error: Cannot find module ‘/v…...

【AIGC】大模型面试高频考点-位置编码篇

【AIGC】大模型面试高频考点-位置编码篇 &#xff08;一&#xff09;手撕 绝对位置编码 算法&#xff08;二&#xff09;手撕 可学习位置编码 算法&#xff08;三&#xff09;手撕 相对位置编码 算法&#xff08;四&#xff09;手撕 Rope 算法&#xff08;旋转位置编码&#xf…...

钓鱼攻击详解:鱼叉攻击与水坑攻击

钓鱼攻击详解&#xff1a;鱼叉攻击与水坑攻击 在现代网络安全领域中&#xff0c;钓鱼攻击&#xff08;Phishing&#xff09;是一种最常见且有效的攻击手段。它通过欺骗用户&#xff0c;引导其泄露敏感信息或执行恶意操作&#xff0c;从而为攻击者打开大门。本文将深入介绍两种…...

如何在自动化安全测试中,实现多工具集成与数据融合,以提高对Spring Boot应用程序安全漏洞的检测效率与准确性?

为了在自动化安全测试中实现多工具集成与数据融合&#xff0c;以提高对Spring Boot应用程序安全漏洞的检测效率与准确性&#xff0c;可以采取以下策略和方法&#xff1a; 文章目录 1. 工具选择与集成2. 数据标准化与聚合3. 数据分析与融合4. 持续改进5. 实施示例 1. 工具选择与…...

框架篇面试

一、Spring框架中的单例bean的安全性 Spring框架中有一个Scope注解&#xff0c;默认的值就是singleton&#xff0c;单例的&#xff1b;因为一般在spring的bean中注入的都是无状态的对象&#xff0c;所以没有线程安全问题。但是如果在bean中定义了可修改的成员变量&#xff0c;…...

STM32滴答定时器SysTick理解+时基设置(4.1)

文章目录 1. 什么是滴答定时器&#xff1f;2. SysTick定时器初始化2.1 systick定时器时钟源&#xff1f;2.2 定时器四个寄存器 3 函数设置3.1SysTick_Config&#xff08;uint32_t ticks&#xff09;函数3.2初始化函数 4. 延时函数实现4.1 ms延时思路及实现4.2 us延时 1. 什么是…...

数字化时代下的企业合规管理:全球化背景下的挑战与机遇

在全球化浪潮的推动下&#xff0c;企业合规管理已成为企业发展中不可或缺的一部分。随着各国法规日益严格&#xff0c;以及数字化技术的飞速发展&#xff0c;企业在扩展业务的同时&#xff0c;也面临着越来越多的合规挑战。有效的合规管理不仅有助于提高企业的管理水平和运营效…...

读《Effective Java》笔记 - 条目17

条目17&#xff1a;使可变性最小化 为什么要使可变性最小化&#xff1f; 不可变对象天然是线程安全的&#xff0c;可以在多个线程之间安全共享。而可变对象需要添加额外的同步机制保证线程安全。不可变对象一旦创建就不会改变&#xff0c;便于追踪和理解代码。而可变对象的状态…...

对比json数据是否变化

在 JavaScript 中&#xff0c;你可以使用多种方法来对比两个 JSON 数据是否发生变化。以下是几种常见的方式&#xff1a; 1. 使用 JSON.stringify 最简单的方法是将两个 JSON 对象序列化为字符串&#xff0c;并比较这些字符串。但需要注意的是&#xff0c;这种方法对于对象属…...

云计算实验室建设方案

一、云计算实验室建设方案 云计算实验教学整体解决方案&#xff0c;包括&#xff1a;云计算服务器集群、云计算实训平台、实训课程体系、行业实战课程系统、行业数据等&#xff0c;系统性地解决云计算实训教学的痛点问题。 【硬件系统】云计算实训一体机 云计算实训一体机是唯…...

一、理论基础-PSI

之前参加了隐语第2期&#xff0c;对隐语SecretFlow框架有了大致的了解&#xff0c;这次参加隐语第4期&#xff0c;学习下PSI和PIR。 一、PSI定义 首先介绍PSI的定义&#xff0c;PSI&#xff08;隐私集合求交&#xff0c;Private Set Intersection即PSI)是安全多方计算&#x…...

C++学习0.2: RAII

引用&#xff1a; 【代码质量】RAII在C编程中的必要性_raii 在c中的重要性-CSDN博客 C RAII典型应用之lock_guard和unique_lock模板_raii lock-CSDN博客 前言: 常用的线程间同步/通信&#xff08;IPC&#xff09;方式有锁&#xff08;互斥锁、读写锁、自旋锁&#xff09;、…...

机器学习基础

了解机器学习的基本概念&#xff0c;如监督学习、无监督学习、强化学习、模型评估指标&#xff08;准确率、召回率、F1分数等&#xff09;。 机器学习&#xff08;Machine Learning&#xff0c;ML&#xff09;是人工智能&#xff08;AI&#xff09;的一个分支&#xff0c;它使计…...

传输层TCP_三次握手四次挥手的过程

三次握手四次挥手 三次握手 三次握手...

AI主流的生成式工作流框架

根据搜索结果&#xff0c;以下是一些2024年比较主流的生成式工作流框架&#xff1a; 1. LangChain&#xff1a;LangChain是一个用于构建生成式AI工作流的开发框架&#xff0c;它支持多种语言模型、工具、数据源及其他系统的集成。 2. DSPy&#xff1a;DSPy是一个生成式AI工作…...

【WRF后处理】WRF时区(UTC)需转化为北京时间(CST)!!!

目录 WRF运行时间标准注意事项-本地时区问题 输入数据&#xff1a;ERA5时间标准ERA5数据和WRF模型需要转换为北京时间&#xff01;&#xff01;&#xff01;北京时间&#xff08;CST&#xff09;与协调世界时&#xff08;UTC&#xff09;的关系转换方法 参考 WRF运行时间标准 …...

Qt 2D绘图之五:图形视图框架的结构、坐标系统和框架间的事件处理与传播

参考文章链接: Qt 2D绘图之五:图形视图框架的结构和坐标系统 Qt 2D绘图之六:图形视图框架的事件处理与传播 图形视图框架的结构 在前面讲的基本绘图中,我们可以自己绘制各种图形,并且控制它们。但是,如果需要同时绘制很多个相同或不同的图形,并且要控制它们的移动、…...

游戏引擎学习第34天

仓库:https://gitee.com/mrxiao_com/2d_game #这天内容比较多 开场介绍 游戏开发行业的基础是使用C和C编程&#xff0c;这是当今几乎所有游戏的开发标准。市面上广受欢迎的游戏&#xff0c;如《使命召唤》或《侠盗猎车手》&#xff0c;它们的底层代码和引擎几乎无一例外地采…...

深度学习笔记——模型压缩和优化技术(蒸馏、剪枝、量化)

本文详细介绍模型训练完成后的压缩和优化技术&#xff1a;蒸馏、剪枝、量化。 文章目录 1. 知识蒸馏 (Knowledge Distillation)基本概念工作流程关键技术类型应用场景优势与挑战优势挑战 总结 2. 权重剪枝 (Model Pruning)基本原理二分类1. 非结构化剪枝&#xff08;Unstructur…...

[在线实验]-RabbitMQ镜像的下载与部署

镜像下载 docker的rabbitmq镜像资源-CSDN文库 加载镜像 docker load --input rabbitmq.tar 给镜像打标签 这里发现镜像名为none&#xff0c;需要给镜像重命名下 docker tag [镜像id] [新镜像名称]:[新镜像标签] docker tag ebaf409ffbe2 rabbitmq:management 运行镜像…...

Netty 入门应用:结合 Redis 实现服务器通信

在上篇博客中&#xff0c;我们了解了 Netty 的基本概念和架构。本篇文章将带你深入实践&#xff0c;构建一个简单的 Netty 服务端&#xff0c;并结合 Redis 实现一个数据存取的示例。在这个场景中&#xff0c;Redis 作为缓存存储&#xff0c;Netty 作为服务端处理客户端请求。通…...

推荐 编译器c++

网页型 https://www.acgo.cn/playground C 在线工具 | 菜鸟工具 AcWing - 在线题库 ZJYYC在线测评系统 少儿编程竞赛在线学习 登录 - JOYSKID 余博士教编程_酷哥OJ_酷哥爱编程_酷哥创客AI编程 登录 - Luogu Spilopelia 软件型 DEV-c Dev C软件下载...

【新品发布】ESP32-P4开发板 —— 启明智显匠心之作,为物联网及HMI产品注入强劲动力

核心亮点&#xff1a; ESP32-P4开发板&#xff0c;是启明智显精心打造的一款高性能物联网开发板。它专为物联网项目及HMI&#xff08;人机界面&#xff09;产品而设计&#xff0c;旨在为您提供卓越的性能和稳定可靠的运行体验。 强大硬件配置&#xff1a; 双核400MHz RISC-V处…...

MeterSphere 使用脚本处理数据

1、前置/后置脚本 支持BeanShell(JSR223)、python、groovy、JavaScript脚本语言&#xff0c;推荐BeanShell(JSR223)。 在前置脚本中可以直接引用JMeter 预定义对象&#xff0c;例如&#xff1a; -- log&#xff1a;用于在脚本执行过程中打印日志 //打印“Hello World!”到info…...

如何获取谷歌新闻API密钥?

在信息获取和新闻传播领域&#xff0c;快速获取最新的新闻动态至关重要。谷歌新闻API为开发者提供了强大的工具&#xff0c;能够方便地集成全球各类新闻内容。通过使用该API&#xff0c;开发者可以实现对新闻的实时访问和管理&#xff0c;为用户提供丰富的信息服务。本文将指导…...

【全网最新】若依管理系统基于SpringBoot的前后端分离版本开发环境配置

目录 提前准备&#xff1a; 下载源代码 设置依赖 设置后台连接信息 运行后台 运行前端 安装npm依赖 启动前端 登录网页客户端 提前准备&#xff1a; 1、安装mysql 5以上就可以。 2、安装redis. 3、安装npm npm下载地址&#xff1a;https://nodejs.org/dist/v22.12…...

备赛蓝桥杯--算法题目(3)

1. 2的幂 231. 2 的幂 - 力扣&#xff08;LeetCode&#xff09; class Solution { public:bool isPowerOfTwo(int n) {return n>0&&n(n&(-n));} }; 2. 3的幂 326. 3 的幂 - 力扣&#xff08;LeetCode&#xff09; class Solution { public:bool isPowerOfT…...

如何解决 java.nio.charset.CoderMalfunctionError: 编码器故障错误问题?亲测有效的解决方法!

java.nio.charset.CoderMalfunctionError 是一个在 Java 中相对较少遇到的异常&#xff0c;通常与字符编码转换过程中的错误有关。当 Java 程序在进行字符编码转换时&#xff0c;遇到无法处理的字符或编码故障时&#xff0c;就会抛出该异常。 1. 问题描述 java.nio.charset.C…...

电气自动化 基于PLC控制的四路抢答器设计

摘要 本文描述了一款用三菱FX3U-48M可编程控制器设计的四路抢答器的系统构成、设计思路和功能。此抢答系统除了有基本抢答功能之外&#xff0c;还有计时、计算得分、亮灯提提示以及蜂鸣提醒功能。程序中设定答题时间&#xff0c;在主持人未按下开始抢答按钮之前&#xff0c;选…...

GA优化后的RBF神经网络

遗传算法&#xff08;Genetic Algorithm, GA&#xff09;优化后的RBF&#xff08;Radial Basis Function&#xff09;神经网络是一种结合进化算法与神经网络的混合模型&#xff0c;用于改进RBF神经网络的性能。以下是该模型的基本原理和相关公式&#xff1a; clear all close a…...

Scala:正则表达式

object test03 {//正则表达式def main(args: Array[String]): Unit {//定义一个正则表达式//1.[ab]:表示匹配一个字符&#xff0c;或者是a&#xff0c;或者是b//2.[a-z]:表示从a到z的26个字母中的任意一个//3.[A-Z]:表示从A到Z的26个字母中的任意一个//4.[0-9]:表示从0到9的10…...

vulnhub靶场之【hacksudo】1.0.1

前言 靶机&#xff1a;hacksudo 192.168.1.45 攻击&#xff1a;kali 192.168.1.16 都是虚拟机环境&#xff0c;桥接模式 主机发现 使用netdiscover或者arp-scan -l扫描 netdiscover -r 192.168.1.1/24信息收集 使用nmap扫描 因为看到2222是ssh服务&#xff0c;所以又扫…...

第4章:颜色和背景 --[CSS零基础入门]

在 CSS 中&#xff0c;颜色和背景属性是用于美化网页元素的重要工具。你可以通过多种方式定义颜色&#xff0c;并且可以设置元素的背景颜色、图像、渐变等。以下是关于如何在 CSS 中使用颜色和背景的一些关键点和示例。 1.颜色表示法 当然&#xff01;以下是使用不同颜色表示…...

Python实现PBKDF2_SHA256加密密码

加密保存格式&#xff1a;pbkdf2_sha256$迭代次数$盐$哈希值 admin可能的结果:pbkdf2_sha256$10000$yzsusUJwrGfonwZzVxlnA$vgf/OgLf5C4wtQLtfNY9d68Hhxgv8eqZ0mwfxCqqeU import os import hashlib import base64 def password_encrypt(password, saltNone, iterations1000…...