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

数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表

线性表

定义

一个最简单,最基本的数据结构。一个线性表由多个相同类型的元素穿在一次,并且每一个元素都一个前驱(前一个元素)和后继(后一个元素)。

线性表的类型

常见的类型:数组、栈、队列、链表

这些不同数据结构的特性可以解决不同种类的问题

P3156 【深基15.例1】询问学号

题面

题目描述

有 n(n≤2×106) 名同学陆陆续续进入教室。我们知道每名同学的学号(在 1 到 109 之间),按进教室的顺序给出。上课了,老师想知道第 i 个进入教室的同学的学号是什么(最先进入教室的同学 i=1),询问次数不超过 105 次。

输入格式

第一行 2 个整数 n 和 m,表示学生个数和询问次数。

第二行 n 个整数,表示按顺序进入教室的学号。

第三行 m 个整数,表示询问第几个进入教室的同学。

输出格式

输出 m 个整数表示答案,用换行隔开。

输入输出样例

输入 #1 

10 3
1 9 2 60 8 17 11 4 5 14
1 5 9

输出 #1 

1
8
5

题解

可以直接设计一个数组记录每个学生的学号,并查询那m个询问即可。还有一种做法是使STL中的容器Vector,又称可变长度数组,为了避免空间开的太大儿出现程序性错误。我在介绍STL的一篇博客写到过vector的常用操作例如
vector<int> v;

v.push_back(a);

v.size();

v.resize(n,m); 

等等,因此,这道题可以一个一个把学号读入然后pushback进这个可变长度数组。

代码

#include<iostream>
#include<vector>
using namespace std;int n,m,tmp;
int main(){vector<int> stu;cin>>n>>m;for(int i=0;i<n;i++){cin>>tmp;stu.push_back(tmp);}for(int i=0;i<m;i++){cin>>tmp;cout<<stu[tmp-1]<<endl;}return 0;
}

P3613 【深基15.例2】寄包柜

题面

题目描述

超市里有 n(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一,第 i 个寄包柜有 ai​(1≤ai​≤105) 个格子,不过我们并不知道各个 ai​ 的值。对于每个寄包柜,格子编号从 1 开始,一直到 ai​。现在有 q(1≤q≤105) 次操作:

  • 1 i j k:在第 i 个柜子的第 j 个格子存入物品 k(0≤k≤109)。当 k=0 时说明清空该格子。
  • 2 i j:查询第 i 个柜子的第 j 个格子中的物品是什么,保证查询的柜子有存过东西。

已知超市里共计不会超过 107 个寄包格子,ai​ 是确定然而未知的,但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 n 和 q,寄包柜个数和询问次数。

接下来 q 个整数,表示一次操作。

输出格式

对于查询操作时,输出答案,以换行隔开。

输入输出样例

输入 #1 

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

输出 #1 

118014
1

题解

代码

B3630 排队顺序

题面

题目描述

有 n(2≤n≤106) 个小朋友,他们的编号分别从 1 到 n。现在他们排成了一个队伍,每个小朋友只知道他后面一位小朋友的编号。现在每个小朋友把他后面是谁告诉你了,同时你还知道排在队首的是哪位小朋友,请你从前到后输出队列中每个小朋友的编号。

输入格式

第一行一个整数 n,表示小朋友的人数。

第二行 n 个整数,其中第 i 个数表示编号为 i 的小朋友后面的人的编号。如果这个数是 0,则说明这个小朋友排在最后一个。

第三行一个整数 ℎ,表示排在第一个的小朋友的编号。

输出格式

一行 n 个整数,表示这个队伍从前到后所有小朋友的编号,用空格隔开。

输入输出样例

输入 #1复制

6
4 6 0 2 3 5
1

输出 #1复制

1 4 2 6 5 3

题解

代码

相关文章:

数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表

线性表 定义 一个最简单&#xff0c;最基本的数据结构。一个线性表由多个相同类型的元素穿在一次&#xff0c;并且每一个元素都一个前驱&#xff08;前一个元素&#xff09;和后继&#xff08;后一个元素&#xff09;。 线性表的类型 常见的类型&#xff1a;数组、栈、队列…...

成瘾机制中微生物群的神秘角色

谷禾健康 成瘾是一种大脑疾病&#xff0c;受害者无法控制地对某种物质或行为产生强烈的依赖和渴求&#xff0c;尽管这种行为会产生有害的后果。成瘾包括一系列物质滥用障碍&#xff0c;例如药物、酒精、香烟&#xff0c;过度饮食。近年来&#xff0c;吸毒成瘾急剧上升&#xff…...

arm安装docker与docker-copose

一、银河麒麟Arm64安装docker 1、docker 安装包地址&#xff1a; https://download.docker.com/linux/static/stable 2、解压&#xff0c;然后将docker目录下文件拷贝到/usr/bin里 tar -xf docker-18.09.3.tgz mv docker/* /usr/bin/ 3、准备 docker.service系统配置文件 &…...

9.文件基本操作

第四章 文件管理 9.文件基本操作 ​    “打开文件和关闭文件”与平常鼠标双击打开文件和点击“X”关闭文件是有所不同的。 ​    操作系统在处理open系统调用时主要做了以下两件事情&#xff0c;①根据我们提供的文件存放路径在外存当中找到这个目录对应的目录表&#x…...

【Java】Spring——Bean对象的作用域和生命周期

文章目录 前言一、引出Bean对象的作用域1.普通变量的作用域2.Bean对象的作用域 二、Bean对象的作用域1.Bean对象的6种作用域2.设置Bean对象的作用域 三、Bean对象的生命周期总结 前言 本人是一个普通程序猿!分享一点自己的见解,如果有错误的地方欢迎各位大佬莅临指导,如果你也…...

数字孪生助力智慧水务:科技创新赋能水资源保护

智慧水务中&#xff0c;数字孪生有着深远的作用&#xff0c;正引领着水资源管理和环境保护的创新变革。随着城市化和工业化的不断推进&#xff0c;水资源的可持续利用和管理愈发显得重要&#xff0c;而数字孪生技术为解决这一挑战提供了独特的解决方案。 数字孪生技术&#xf…...

css 实现文字横向循环滚动

实现效果 思路 ## 直接上代码,html部分 //我这里是用的uniapp <view class"weather_info_wrap"><view class"weather_info">当前多云&#xff0c;今晚8点转晴&#xff0c;明天有雨&#xff0c;温度32摄氏度。</view><view class&qu…...

VuePress 数学公式支持

前言 博主在为 VuePress1.0 博客添加数学公式支持过程中遇到如下问题 问题一 在配置诸如 markdown-it-texmath,markdown-it-katex,markdown-it-mathjax3 这些插件后遇到 Error: Dynamic require of "XXX" is not supported 问题二 配置插件 vuepress-plugin-ma…...

stm32控制蜂鸣器源代码(附带proteus线路图)

说明&#xff1a; 1 PB0输出0时&#xff0c;蜂鸣器发生&#xff1b; 2 蜂鸣器电阻值如果太大会导致电流太小&#xff0c;发不出声音&#xff1b; 3蜂鸣器额定电压需要设置得低一点&#xff0c;可以是2V&#xff0c;但不能高于3V&#xff0c;这更右上角的电阻值有关系&#x…...

selinux

一、selinux的说明 二、selinux的工作原理 三、selinux的启动、关闭与查看 Enforcing和permissive都是临时的&#xff0c;重启还是依据配置文件中&#xff0c;禁用selinux&#xff0c;修改配置文件&#xff1a; 之后重启生效 四、selinux对linux服务的影响...

使用opencv4.7.0部署yolov5

yolov5原理和部署原理就不说了&#xff0c;想了解的可以看看这篇部署原理文章 #include <fstream> #include <sstream> #include <iostream> #include <opencv2/dnn.hpp> #include <opencv2/imgproc.hpp> #include <opencv2/highgui.hpp>/…...

Python - 协程基本使用详解【demo】

一. 前言 协程&#xff08;Coroutine&#xff09;是一种轻量级的线程&#xff0c;也被称为用户级线程或绿色线程。它是一种用户态的上下文切换方式&#xff0c;比内核态的线程切换更为轻量级&#xff0c;能够高效的支持大量并发操作。 2. 使用协程的好处 Python 中的协程是通…...

Android MVVM架构模式,详详详细学习

MVVM&#xff08;Model-View-ViewModel&#xff09; 是一种基于数据绑定的架构模式&#xff0c;用于设计和组织应用程序的代码结构。它将应用程序分为三个主要部分&#xff1a;Model&#xff08;模型&#xff09;、View&#xff08;视图&#xff09;和ViewModel&#xff08;视…...

亿赛通电子文档安全管理系统 RCE漏洞复现

0x01 产品简介 亿赛通电子文档安全管理系统&#xff08;简称&#xff1a;CDG&#xff09;是一款电子文档安全加密软件&#xff0c;该系统利用驱动层透明加密技术&#xff0c;通过对电子文档的加密保护&#xff0c;防止内部员工泄密和外部人员非法窃取企业核心重要数据资产&…...

星际争霸之小霸王之小蜜蜂(三)--重构模块

目录 前言 一、为什么要重构模块 二、创建game_functions 三、创建update_screen() 四、修改alien_invasion模块 五、课后思考 总结 前言 前两天我们已经成功创建了窗口&#xff0c;并将小蜜蜂放在窗口的最下方中间位置&#xff0c;本来以为今天将学习控制小蜜蜂&#xff0c;结…...

JS的解析与Js2Py使用

JS的解析与Js2Py使用 JS的解析事件监听器搜索关键字请求关联JS文件 Js2PyJs2Py的简单使用安装Js2Py执行JavaScript代码调用JavaScript函数 Js2Py的应用示例创建JavaScript文件使用JavaScript JS的解析 在一个网站中&#xff0c;登录密码通常是会进行加密操作的&#xff0c;那么…...

Spring Bean的生命周期总结(包含面试题)

目录 一、Bean的初始化过程 1. 加载Spring Bean 2. 解析Bean的定义 3. Bean属性定义 4. BeanFactoryPostProcessor 扩展接口 5. 实例化Bean对象 6. Aware感知 7. 初始化方法 8. 后置处理 9. destroy 销毁 二、Bean的单例与多例模式 2.1 单例模式&#xff08;Sin…...

SpringjDBCTemplate_spring25

1、首先导入两个包&#xff0c;里面有模板 2、transtion事务 jDbc操作对象&#xff0c;底层默认的是事务&#xff1a; 3、我们java一般对实体类进行操作。 4、第一步写好坐标。 创建一个Account表 数据修改用update 数据进去了...

设计模式——桥接模式

引用 桥我们大家都熟悉&#xff0c;顾名思义就是用来将河的两岸联系起来的。而此处的桥是用来将两个独立的结构联系起来&#xff0c;而这两个被联系起来的结构可以独立的变化&#xff0c;所有其他的理解只要建立在这个层面上就会比较容易。 基本介绍 桥接模式&#xff08;Br…...

改进YOLO系列:2.添加ShuffleAttention注意力机制

添加ShuffleAttention注意力机制 1. ShuffleAttention注意力机制论文2. ShuffleAttention注意力机制原理3. ShuffleAttention注意力机制的配置3.1common.py配置3.2yolo.py配置3.3yaml文件配置1. ShuffleAttention注意力机制论文 论文题目:SA-NET: SHUFFLE ATTENTION …...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

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

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

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

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

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...