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中链表的局限性:
- 迭代器访问速度:虽然 在操作上有良好的时间复杂度,但它并不具备随机访问特性。 每次访问某个特定元素时,都需要从头或尾遍历链表到该位置,这会导致性能问题。
list
- 内存分配: 会频繁进行内存分配和释放,尤其是在链表的大小较大时,这可能导致额外的内存管理开销。
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 单向链表-模拟链表
来源 :题目链接-洛谷 B3631 单向链表 单向链表 题目描述 实现一个数据结构,维护一张表(最初只有一个元素 1 1 1)。需要支持下面的操作,其中 x x x 和 y y y 都是 1 1 1 到 1 0 6 10^6 106 范围内的正整数&…...
【C++】格式化输出详解:掌握 cout 的进阶用法
博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯格式化输出的理论概述💯控制输出宽度和填充字符setw 操作符setfill 操作符 💯控制浮点数的显示格式fixed 与 scientificsetprecision 💯…...
【NoSQL数据库】Hbase基本操作——数据库表的增删改查
目录 一、Hbase原理 二、HBase数据库操作 三、遇到的问题和解决方法 一、Hbase原理 HBase的数据模型: 行键 时间戳 列族:contents 列族:anchor 列族:mime “com.cnn.www” T9 Achor:cnnsi.com”CNN” T8 Achor:…...
同步fifo
同步FIFO FIFO即是一种先进先出的数据缓存器。同步FIFO指的是数据的写入和读出的时钟是同一个时钟。异步 FIFO 有两个时钟信号,读和写逻辑用的各自的读写时钟。 FIFO没有外部读写地址线,使用起来简单。但是缺点就是只能先入先出,数据地址由…...
肌肉骨骼肿瘤治疗市场:潜力无限,未来可期
肌肉骨骼肿瘤治疗作为现代医学的重要分支,专注于应对骨骼和肌肉系统中的良性和恶性肿瘤。随着全球人口老龄化和生活方式的改变,肌肉骨骼疾病日益成为公共卫生的重要问题。与此同时,医疗技术的进步和患者对高质量医疗服务的需求不断推动该市场…...
高考倒计时:用倒计时软件 为梦想加油 可用于教室黑板或者电脑上
高考,这个被无数学子视为人生重要转折点的考试,即将来临。每一年的六月,都充满了紧张与期待。如何在这场人生的战役中取得胜利?除了日常的勤奋学习,科学的复习计划和心态调整外,一款好用的倒计时软件&#…...
人工智能学习用的电脑安装cuda、torch、conda等软件,版本的选择以及多版本切换
接触人工智能的学习三个月了,每天与各种安装包作斗争,缺少依赖包、版本高了、版本低了、不兼容了、系统做一半从头再来了。。。这些都是常态。三个月把单位几台电脑折腾了不下几十次安装,是时候总结一下踩过的坑和积累的经验了。 以一个典型的…...
BERT模型的输出格式探究以及提取出BERT 模型的CLS表示,last_hidden_state[:, 0, :]用于提取每个句子的CLS向量表示
说在前面 最近使用自己的数据集对bert-base-uncased进行了二次预训练,只使用了MLM任务,发现在加载训练好的模型进行输出CLS表示用于下游任务时,同一个句子的输出CLS表示都不一样,并且控制台输出以下警告信息。说是没有这些权重。…...
InfluxDB 集成 Grafana
将InfluxDB集成到Grafana进行详细配置通常包括以下几个步骤:安装与配置InfluxDB、安装与配置Grafana、在Grafana中添加InfluxDB数据源以及创建和配置仪表板。以下是一个详细的配置指南: 一、安装与配置InfluxDB 下载与安装: 从InfluxDB的官…...
Vue跨标签通讯(本地存储)(踩坑)
我司有一个需求【用户指引】 需求是根标签有一个用户指引总开关,可以控制页面所有的用户指引是否在页面进入后初始是否默认打开,但是有些页面会新开标签这就设计到跨标签通讯了 我采取的方案是本地存储 重点:首先本地存储在页面是同源(即域名协议端口三…...
掌握创意之钥:全面解析HTML5 Canvas
在数字时代,表达创意的方式多种多样,而 HTML5 中的 <canvas> 元素无疑为网页开发者提供了一个强大的工具箱。无论你是想要创建动态图表、互动游戏还是复杂的可视化应用,掌握 Canvas 的基本用法都是迈向成功的关键一步。本文将带你一步步…...
mac port 安装redis 并设置为系统服务 自定义配置方法
mac系统中,port 包管理工具比brew的速度快N倍,今天就给大家分享一下在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:多模态交互视野的考察 论文地址:https://arxiv.org/abs/2401.03568 图1:可以在不同领域和应用程序中感知和行动的Agent AI系统概述。Agent AI是正在成为通用人工智能(AGI)的一个有前途的途径。Agent AI培训已经证…...
二百七十八、ClickHouse——将本月第一天所在的那一周视为第一周,无论它是从周几开始的,查询某个日期是本月第几周
一、目的 ClickHouse指标表中有个字段week_of_month,含义是这条数据属于本月第几周。 而且将本月第一天所在的那一周视为第一周,无论它是从周几开始的。比如2024-12-01是周日,即12月第一周。而2024-12-02是周一,即12月第二周 二…...
Unity 相机旋转及角度限制
前言 由于欧拉角具有直观的可读性,做相机旋转时选择修改eulerAngles 来实现旋转,但实际效果与预期稍有不同,这是因为欧拉角受到万向锁(Gimbal Lock)的影响,在赋值时需要对输入的角度进行调整。 if (value…...
基于CentOS系统利用Kamailio搭建企业级SIP服务器
一、Kamailio简介 Kamailio是一款开源的SIP服务器,具有高性能、可扩展、模块化等特点。它广泛应用于VoIP、即时通讯、视频会议等领域。Kamailio支持多种操作系统,如Linux、FreeBSD等,可以与其他开源项目(如 Asterisk、FreeSWITCH…...
部署项目报错
vue2项目部署后 Error: Cannot find module /views/*** 1.起因 登录页、首页等静态页面可以正常进入,后端访问也正常,可以获取到验证码。 但是登录之后会发现首页空白或者进入不到首页 F12查看有报错信息:Error: Cannot find module ‘/v…...
【AIGC】大模型面试高频考点-位置编码篇
【AIGC】大模型面试高频考点-位置编码篇 (一)手撕 绝对位置编码 算法(二)手撕 可学习位置编码 算法(三)手撕 相对位置编码 算法(四)手撕 Rope 算法(旋转位置编码…...
钓鱼攻击详解:鱼叉攻击与水坑攻击
钓鱼攻击详解:鱼叉攻击与水坑攻击 在现代网络安全领域中,钓鱼攻击(Phishing)是一种最常见且有效的攻击手段。它通过欺骗用户,引导其泄露敏感信息或执行恶意操作,从而为攻击者打开大门。本文将深入介绍两种…...
如何在自动化安全测试中,实现多工具集成与数据融合,以提高对Spring Boot应用程序安全漏洞的检测效率与准确性?
为了在自动化安全测试中实现多工具集成与数据融合,以提高对Spring Boot应用程序安全漏洞的检测效率与准确性,可以采取以下策略和方法: 文章目录 1. 工具选择与集成2. 数据标准化与聚合3. 数据分析与融合4. 持续改进5. 实施示例 1. 工具选择与…...
框架篇面试
一、Spring框架中的单例bean的安全性 Spring框架中有一个Scope注解,默认的值就是singleton,单例的;因为一般在spring的bean中注入的都是无状态的对象,所以没有线程安全问题。但是如果在bean中定义了可修改的成员变量,…...
STM32滴答定时器SysTick理解+时基设置(4.1)
文章目录 1. 什么是滴答定时器?2. SysTick定时器初始化2.1 systick定时器时钟源?2.2 定时器四个寄存器 3 函数设置3.1SysTick_Config(uint32_t ticks)函数3.2初始化函数 4. 延时函数实现4.1 ms延时思路及实现4.2 us延时 1. 什么是…...
数字化时代下的企业合规管理:全球化背景下的挑战与机遇
在全球化浪潮的推动下,企业合规管理已成为企业发展中不可或缺的一部分。随着各国法规日益严格,以及数字化技术的飞速发展,企业在扩展业务的同时,也面临着越来越多的合规挑战。有效的合规管理不仅有助于提高企业的管理水平和运营效…...
读《Effective Java》笔记 - 条目17
条目17:使可变性最小化 为什么要使可变性最小化? 不可变对象天然是线程安全的,可以在多个线程之间安全共享。而可变对象需要添加额外的同步机制保证线程安全。不可变对象一旦创建就不会改变,便于追踪和理解代码。而可变对象的状态…...
对比json数据是否变化
在 JavaScript 中,你可以使用多种方法来对比两个 JSON 数据是否发生变化。以下是几种常见的方式: 1. 使用 JSON.stringify 最简单的方法是将两个 JSON 对象序列化为字符串,并比较这些字符串。但需要注意的是,这种方法对于对象属…...
云计算实验室建设方案
一、云计算实验室建设方案 云计算实验教学整体解决方案,包括:云计算服务器集群、云计算实训平台、实训课程体系、行业实战课程系统、行业数据等,系统性地解决云计算实训教学的痛点问题。 【硬件系统】云计算实训一体机 云计算实训一体机是唯…...
一、理论基础-PSI
之前参加了隐语第2期,对隐语SecretFlow框架有了大致的了解,这次参加隐语第4期,学习下PSI和PIR。 一、PSI定义 首先介绍PSI的定义,PSI(隐私集合求交,Private Set Intersection即PSI)是安全多方计算&#x…...
C++学习0.2: RAII
引用: 【代码质量】RAII在C编程中的必要性_raii 在c中的重要性-CSDN博客 C RAII典型应用之lock_guard和unique_lock模板_raii lock-CSDN博客 前言: 常用的线程间同步/通信(IPC)方式有锁(互斥锁、读写锁、自旋锁)、…...
机器学习基础
了解机器学习的基本概念,如监督学习、无监督学习、强化学习、模型评估指标(准确率、召回率、F1分数等)。 机器学习(Machine Learning,ML)是人工智能(AI)的一个分支,它使计…...
传输层TCP_三次握手四次挥手的过程
三次握手四次挥手 三次握手 三次握手...
AI主流的生成式工作流框架
根据搜索结果,以下是一些2024年比较主流的生成式工作流框架: 1. LangChain:LangChain是一个用于构建生成式AI工作流的开发框架,它支持多种语言模型、工具、数据源及其他系统的集成。 2. DSPy:DSPy是一个生成式AI工作…...
【WRF后处理】WRF时区(UTC)需转化为北京时间(CST)!!!
目录 WRF运行时间标准注意事项-本地时区问题 输入数据:ERA5时间标准ERA5数据和WRF模型需要转换为北京时间!!!北京时间(CST)与协调世界时(UTC)的关系转换方法 参考 WRF运行时间标准 …...
Qt 2D绘图之五:图形视图框架的结构、坐标系统和框架间的事件处理与传播
参考文章链接: Qt 2D绘图之五:图形视图框架的结构和坐标系统 Qt 2D绘图之六:图形视图框架的事件处理与传播 图形视图框架的结构 在前面讲的基本绘图中,我们可以自己绘制各种图形,并且控制它们。但是,如果需要同时绘制很多个相同或不同的图形,并且要控制它们的移动、…...
游戏引擎学习第34天
仓库:https://gitee.com/mrxiao_com/2d_game #这天内容比较多 开场介绍 游戏开发行业的基础是使用C和C编程,这是当今几乎所有游戏的开发标准。市面上广受欢迎的游戏,如《使命召唤》或《侠盗猎车手》,它们的底层代码和引擎几乎无一例外地采…...
深度学习笔记——模型压缩和优化技术(蒸馏、剪枝、量化)
本文详细介绍模型训练完成后的压缩和优化技术:蒸馏、剪枝、量化。 文章目录 1. 知识蒸馏 (Knowledge Distillation)基本概念工作流程关键技术类型应用场景优势与挑战优势挑战 总结 2. 权重剪枝 (Model Pruning)基本原理二分类1. 非结构化剪枝(Unstructur…...
[在线实验]-RabbitMQ镜像的下载与部署
镜像下载 docker的rabbitmq镜像资源-CSDN文库 加载镜像 docker load --input rabbitmq.tar 给镜像打标签 这里发现镜像名为none,需要给镜像重命名下 docker tag [镜像id] [新镜像名称]:[新镜像标签] docker tag ebaf409ffbe2 rabbitmq:management 运行镜像…...
Netty 入门应用:结合 Redis 实现服务器通信
在上篇博客中,我们了解了 Netty 的基本概念和架构。本篇文章将带你深入实践,构建一个简单的 Netty 服务端,并结合 Redis 实现一个数据存取的示例。在这个场景中,Redis 作为缓存存储,Netty 作为服务端处理客户端请求。通…...
推荐 编译器c++
网页型 https://www.acgo.cn/playground C 在线工具 | 菜鸟工具 AcWing - 在线题库 ZJYYC在线测评系统 少儿编程竞赛在线学习 登录 - JOYSKID 余博士教编程_酷哥OJ_酷哥爱编程_酷哥创客AI编程 登录 - Luogu Spilopelia 软件型 DEV-c Dev C软件下载...
【新品发布】ESP32-P4开发板 —— 启明智显匠心之作,为物联网及HMI产品注入强劲动力
核心亮点: ESP32-P4开发板,是启明智显精心打造的一款高性能物联网开发板。它专为物联网项目及HMI(人机界面)产品而设计,旨在为您提供卓越的性能和稳定可靠的运行体验。 强大硬件配置: 双核400MHz RISC-V处…...
MeterSphere 使用脚本处理数据
1、前置/后置脚本 支持BeanShell(JSR223)、python、groovy、JavaScript脚本语言,推荐BeanShell(JSR223)。 在前置脚本中可以直接引用JMeter 预定义对象,例如: -- log:用于在脚本执行过程中打印日志 //打印“Hello World!”到info…...
如何获取谷歌新闻API密钥?
在信息获取和新闻传播领域,快速获取最新的新闻动态至关重要。谷歌新闻API为开发者提供了强大的工具,能够方便地集成全球各类新闻内容。通过使用该API,开发者可以实现对新闻的实时访问和管理,为用户提供丰富的信息服务。本文将指导…...
【全网最新】若依管理系统基于SpringBoot的前后端分离版本开发环境配置
目录 提前准备: 下载源代码 设置依赖 设置后台连接信息 运行后台 运行前端 安装npm依赖 启动前端 登录网页客户端 提前准备: 1、安装mysql 5以上就可以。 2、安装redis. 3、安装npm npm下载地址:https://nodejs.org/dist/v22.12…...
备赛蓝桥杯--算法题目(3)
1. 2的幂 231. 2 的幂 - 力扣(LeetCode) class Solution { public:bool isPowerOfTwo(int n) {return n>0&&n(n&(-n));} }; 2. 3的幂 326. 3 的幂 - 力扣(LeetCode) class Solution { public:bool isPowerOfT…...
如何解决 java.nio.charset.CoderMalfunctionError: 编码器故障错误问题?亲测有效的解决方法!
java.nio.charset.CoderMalfunctionError 是一个在 Java 中相对较少遇到的异常,通常与字符编码转换过程中的错误有关。当 Java 程序在进行字符编码转换时,遇到无法处理的字符或编码故障时,就会抛出该异常。 1. 问题描述 java.nio.charset.C…...
电气自动化 基于PLC控制的四路抢答器设计
摘要 本文描述了一款用三菱FX3U-48M可编程控制器设计的四路抢答器的系统构成、设计思路和功能。此抢答系统除了有基本抢答功能之外,还有计时、计算得分、亮灯提提示以及蜂鸣提醒功能。程序中设定答题时间,在主持人未按下开始抢答按钮之前,选…...
GA优化后的RBF神经网络
遗传算法(Genetic Algorithm, GA)优化后的RBF(Radial Basis Function)神经网络是一种结合进化算法与神经网络的混合模型,用于改进RBF神经网络的性能。以下是该模型的基本原理和相关公式: clear all close a…...
Scala:正则表达式
object test03 {//正则表达式def main(args: Array[String]): Unit {//定义一个正则表达式//1.[ab]:表示匹配一个字符,或者是a,或者是b//2.[a-z]:表示从a到z的26个字母中的任意一个//3.[A-Z]:表示从A到Z的26个字母中的任意一个//4.[0-9]:表示从0到9的10…...
vulnhub靶场之【hacksudo】1.0.1
前言 靶机:hacksudo 192.168.1.45 攻击:kali 192.168.1.16 都是虚拟机环境,桥接模式 主机发现 使用netdiscover或者arp-scan -l扫描 netdiscover -r 192.168.1.1/24信息收集 使用nmap扫描 因为看到2222是ssh服务,所以又扫…...
第4章:颜色和背景 --[CSS零基础入门]
在 CSS 中,颜色和背景属性是用于美化网页元素的重要工具。你可以通过多种方式定义颜色,并且可以设置元素的背景颜色、图像、渐变等。以下是关于如何在 CSS 中使用颜色和背景的一些关键点和示例。 1.颜色表示法 当然!以下是使用不同颜色表示…...
Python实现PBKDF2_SHA256加密密码
加密保存格式:pbkdf2_sha256$迭代次数$盐$哈希值 admin可能的结果:pbkdf2_sha256$10000$yzsusUJwrGfonwZzVxlnA$vgf/OgLf5C4wtQLtfNY9d68Hhxgv8eqZ0mwfxCqqeU import os import hashlib import base64 def password_encrypt(password, saltNone, iterations1000…...