备考蓝桥杯:顺序表相关算法题


目录

询问学号

寄包柜

移动0

颜色分类

合并两个有序数组

物品移动


询问学号

我们的思路:创建一个顺序表存储从1开始依次存放进入教室的学生学号,然后查询

#include <iostream>
#include <vector>
using namespace std;
const int N = 2e6+10;//表示教室最多进入学生个数
int main()
{int n,m;cin >> n >> m;vector <int> a1(N);for(int i = 1;i<=n;i++){cin >> a1[i];//输入进入学生的学号}int t;for(int i = 0;i<m;i++){cin >> t;cout << a1[t] << endl;//输出查询到的学号}
}

寄包柜

一共有n个柜子,每个柜子里又有ai个格子,格子里存放物品

我们需要创建一个二维数组,创建二维数组的方式有两个 一种是a[][]

一种是vector <int> a[] 由于我们这里主要是用vector解决问题,所以我们选择vector

注意:顺序表要定义在主函数外面,不然会有栈溢出的风险

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5+10;
vector<int> a[N];//这里初始化每个vector<int>的顺序表空间都是0的,所以我们后续存格子需要扩容
int main()
{int n,q;cin >> n >> q;//输入n个柜子,q次操作int k,i,j;//k是物品数,i是第i个柜子,j是第j个格子while(q--){int op;cin >> op >> i >> j;if(op ==1)//op为1的时候进行放物品的操作,在第i个柜子第j个格子存放k个物品{cin >> k;//存放物品个数if(a[i].size() <= j)//由于编号是从1开始的,所以存第j个物品的话要有j+1个空间{a[i].resize(j+1);}a[i][j] = k;}else{cout << a[i][j]<< endl;}}return 0;
}

移动0

方法1:辅助数组

class Solution {
public:void moveZeroes(vector<int>& nums) {vector <int> nums2(nums.size());int j = 0;for(int i = 0;i<nums.size();i++){if(nums[i] != 0){nums2[j] = nums[i];j++;}}nums = nums2;}
};

方法2,双指针

这种问题就叫数组分块的问题,就是给我们一个条件,让我们把数组左边变为非0右边全变为0,或者左边大于等于某个数,右边小于某个数,这也是快速排序里比较核心的一步,我们可以定义一个cur指针:指向最后一个非零元素,定义一个i指针,扫描数组

[0,cur]永远都是非零元素,[cur+1,i-1]永远都是零元素,[i,n-1]是待扫描区域

那我们遍历顺序表,如果元素是0我们就i++,如果元素是非0那我们就把cur+1并和这个非零元素交换位置,再让i+1扫描下一个元素,最后我们就完成了数组分块操作

class Solution {
public:void moveZeroes(vector<int>& nums) {for (int i =0,cur = -1;i<nums.size();i++){if(nums[i] !=0){swap(nums[i],nums[++cur]);}}}
};

颜色分类

y

我们用sort其实也能通过

class Solution {
public:void sortColors(vector<int>& nums) {sort(nums.begin(),nums.end());}
};

虽然sort能通过,我们还是要学会我们三指针的方法

定义一个left 初始化为-1,i负责扫描数组,right 初始化为n

我们要达到的是数组分三块,所以我们有下面几个要求

[0,left]全为0 [left+1,i-1]全为1,[i,right-1]待扫描 [right,n-1]全为2

所以当我们扫描到的元素是2的时候,我们交换right-1和i的元素并让right--

当我们扫描到的元素是0的时候,我们交换left+1和i位置的元素并让left++,i++

当我们扫描到的元素是1的时候,直接让i++

我们脑子里可以有个动态的画面,当i扫描到0的时候,把这个0划分到0到left区间里,i交换到的一定是1或者0到i-1全是0,所以i继续扫描下一个,如果扫描到1的话直接跳过去,因为left+1到i-1的区间里都是1,如果扫描到2的话就把2划到right到n-1的区间里,那就把2和right-1换一下,right左移。一直到最后,0到left就都是0,left到right就都是1,right到n-1就都是2了

class Solution {
public:void sortColors(vector<int>& nums) {int left = -1,right =nums.size(),i=0;while(i<right){if(nums[i]==1) i++;else if (nums[i] == 2) swap(nums[--right],nums[i]);else swap(nums[i++],nums[++left]);}}
};

合并两个有序数组

方法一,辅助数组

我们建一个辅助数组,然后创建三个指针 cur1 和cur2 和cur都初始化为0

cur1和cur2分别遍历数组1和数组2,比较出小的那个元素放在辅助数组里

直到有一方遍历完,这时候我们再把没遍历完的数组的元素依次拷贝到我们的辅助数组里就好了

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector <int> tmp(m+n);int cur1 =0,cur=0,cur2=0;while(cur1<m && cur2<n){if(nums1[cur1] <= nums2[cur2])  tmp[cur++]=nums1[cur1++];else tmp[cur++]=nums2[cur2++];}while(cur1<m) tmp[cur++] = nums1[cur1++];while(cur2<n) tmp[cur++] = nums2[cur2++];for(int i = 0;i<tmp.size();i++) nums1[i] = tmp[i];}};

方法二:原地合并

原地合并的话,我们还是定义cur,cur1,cur2,然后我们遍历数组1和数组2,如果数组1的元素比数组2的元素小的话就cur1++,cur++,如果数组2的元素小,那就把cur2下标的值给cur,cur++,cur2++,但是这种正序遍历会导致数组1原来的值被覆盖,所以我们还要改变一下策略

我们选择反向遍历,cur指向第一个数组的size的最大位置,也就是合并完的最后一个位置,cur1指向第一个数组的当前有效元素的最大位置,cur2指向数组2的最大位置

遍历数组1和数组2,把大的元素赋值给cur所在的位置

如果有一个数组遍历完了,我们要看还有没有哪个数组没遍历完,如果1数组没遍历完就不用管了,因为我们本来就是在1数组的基础上进行的原地合并,如果2数组的元素没遍历完,我们要再写一个循环把2数组的元素依次插进来

我们来实现一下代码

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int cur = nums1.size()-1;int cur1 = m-1;int cur2 = n-1;while(cur1>=0 && cur2>=0){if(nums1[cur1] >= nums2[cur2]) nums1[cur--] = nums1[cur1--];else nums1[cur--] = nums2[cur2--];}while(cur2>=0){nums1[cur--] = nums2[cur2--];}}

物品移动

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 30;
int n;
vector <int> p[N];//创建n个放木块的槽
PII find(int x)
{for(int i = 0;i<n;i++){for(int j =0;j<p[i].size();j++){if(p[i][j] == x)return {i,j};}}
}
void clean(int x1,int y1)
{int t;for(int j = y1+1;j<p[x1].size();j++){t = p[x1][j];p[t].push_back(t);}p[x1].resize(y1+1);}
void move(int x1,int y1,int x2)//把x1,y1及其以上的木块放在x2上 
{for(int i = y1;i<p[x1].size();i++){p[x2].push_back(p[x1][i]);}p[x1].resize(y1);
}
int main()
{ 
//初始化 cin >> n;string op1,op2;int a,b;for(int i =0;i<n;i++){p[i].push_back(i);}  while(cin >> op1 >> a >> op2 >> b){PII pa = find(a);int x1 = pa.first,y1 = pa.second;PII pb = find(b);int x2 = pb.first,y2 = pb.second;if(x1 == x2)continue;if (op1 == "move"){clean(x1,y1);}if(op2 == "onto"){clean(x2,y2);}move(x1,y1,x2);}for (int i = 0;i<n;i++){cout << i << ":";for(int j = 0;j<p[i].size();j++){cout << " " << p[i][j]; }cout << endl;}}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python入门教程 —— 网络编程

1.网络通信概念 简单来说,网络是用物理链路将各个孤立的工作站或主机相连在一起,组成数据链路,从而达到资源共享和通信的目的。 使用网络的目的,就是为了联通多方然后进行通信,即把数据从一方传递给另外一方。 前面的学习编写的程序都是单机的,即不能和其他电脑上的程…

C#异步多线程——ThreadPool线程池

C#实现异步多线程的方式有多种&#xff0c;以下总结的是ThreadPool的用法。 线程池的特点 线程池受CLR管理&#xff0c;线程的生命周期&#xff0c;任务调度等细节都不需要我们操心了&#xff0c;我们只需要专注于任务实现&#xff0c;使用ThreadPool提供的静态方法把我们的任…

68.基于SpringBoot + Vue实现的前后端分离-心灵治愈交流平台系统(项目 + 论文PPT)

项目介绍 本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将论述心灵治愈交流平台的当前背景以及系统开发的目的&#xff0c;后续章节将严格按照软件开发流程&#xff0c;对系统进…

Linux(上):基本知识篇

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、Linux初识1 Linux简介2 Linux学习环境配置(1)安装Linux(2)FinalShell远程连接Linux服务器二、Linux基础命令1 Linux目录结构,根目录 /2 Linux命令基础(1)什么是命令、命令行?(2)…

Python中的可变对象与不可变对象;Python中的六大标准数据类型哪些属于可变对象,哪些属于不可变对象

Python中的可变对象与不可变对象&#xff1b;Python中的六大标准数据类型哪些属于可变对象&#xff0c;哪些属于不可变对象 Python中的可变对象与不可变对象一、Python的六大标准数据类型1. 数字类型 (Number)2. 字符串 (String)3. 列表 (List)4. 元组 (Tuple)5. 集合 (Set)6. …

VSCode Live Server 插件安装和使用

VSCode Live Server是一个由Ritwick Dey开发的Visual Studio Code扩展插件&#xff0c;它提供了一个带有实时重载功能的本地开发服务器。在VSCode中安装和使用Live Server插件进行实时预览和调试Web应用程序。这将大大提高前端开发效率&#xff0c;使网页设计和开发变得更为流畅…

Personal APP

1、Matlab 2023b https://www.bilibili.com/opus/887246540317392920 https://blog.csdn.net/qq_25719943/article/details/138096918 https://www.jokerdown.com/22886.html 2、Jlink使用技巧 J-Scope虚拟示波器功能 Jlink使用技巧之J-Scope虚拟示波器功能 - 知乎 (zhihu.…

【马来西亚理工大学主办,ACM出版】2025年大数据、通信技术与计算机应用国际学术会议(BDCTA 2025)

2025年大数据、通信技术与计算机应用国际学术会议&#xff08;BDCTA 2025) 2025 International Conference on Big Data, Communication Technology and Computer Applications 2025年2月14-16日 | 马来西亚-吉隆坡 大会官网&#xff1a;更多详情【论文投稿】 主办单位&…

Sprint Boot教程之五十:Spring Boot JpaRepository 示例

Spring Boot JpaRepository 示例 Spring Boot建立在 Spring 之上&#xff0c;包含 Spring 的所有功能。由于其快速的生产就绪环境&#xff0c;使开发人员能够直接专注于逻辑&#xff0c;而不必费力配置和设置&#xff0c;因此如今它正成为开发人员的最爱。Spring Boot 是一个基…

超完整Docker学习记录,Docker常用命令详解

前言 关于国内拉取不到docker镜像的问题&#xff0c;可以利用Github Action将需要的镜像转存到阿里云私有仓库&#xff0c;然后再通过阿里云私有仓库去拉取就可以了。 参考项目地址&#xff1a;使用Github Action将国外的Docker镜像转存到阿里云私有仓库 一、Docker简介 Do…

左神算法基础巩固--3

文章目录 二叉树二叉树的遍历先序遍历中序遍历后序遍历 解答二叉树的宽度优先遍历 在这里插入图片描述 一颗完全二叉树具有以下特征&#xff1a;1.不存在任何一个节点具有右子树但不存在左子树.2.不存在任何一个节点在满足1的情况下左右子树不全且其后续节点不为叶子节点 根据以…

推动多语言语音科技迈向新高度:INTERSPEECH 2025 ML-SUPERB 2.0 挑战赛

随着语音技术在各领域应用的迅速扩展&#xff0c;全球语言与口音的多样性成为技术进一步突破的重大挑战。为了应对这一难题&#xff0c;来自卡内基梅隆大学&#xff08;CMU&#xff09;、斯坦福大学&#xff08;Stanford University&#xff09;、乔治梅森大学(George Mason Un…

IvorySQL 升级指南:从 3.x 到 4.0 的平滑过渡

日前&#xff0c;IvorySQL 4.0 重磅发布&#xff0c;全面支持 PostgreSQL 17&#xff0c;并且增强了对 Oracle 的兼容性。关于 IvorySQL 4.0 的介绍&#xff0c;各位小伙伴可以通过这篇文章回顾&#xff1a;IvorySQL 4.0 发布&#xff1a;全面支持 PostgreSQL 17. 在 IvorySQL…

flink的EventTime和Watermark

时间机制 Flink中的时间机制主要用在判断是否触发时间窗口window的计算。 在Flink中有三种时间概念&#xff1a;ProcessTime、IngestionTime、EventTime。 ProcessTime&#xff1a;是在数据抵达算子产生的时间&#xff08;Flink默认使用ProcessTime&#xff09; IngestionT…

Windows11环境下设置MySQL8字符集utf8mb4_unicode_ci

1.关闭MySQL8的服务CTRLshiftESC&#xff0c;找到MySQL关闭服务即可 2.找到配置文件路径&#xff08;msi版本默认&#xff09; C:\ProgramData\MySQL\MySQL Server 8.0 3.使用管理员权限编辑my.ini文件并保存 # Other default tuning values # MySQL Server Instance Config…

python学习笔记—14—函数

1. 函数 (1) len与my_len str "supercarrydoinb"def my_len(tmp_str):cnt 0for i in tmp_str:cnt 1return cntstr_len_1 len(str) str_len_2 my_len(str) print(f"len {str_len_1}") print(f"my_len {str_len_2}") (2) 函数传参数量不受…

Flink源码解析之:Flink on k8s 客户端提交任务源码分析

Flink on k8s 客户端提交任务源码分析 当我们需要在代码中提交Flink job到kubernetes上时&#xff0c;需要如何做呢&#xff1f;要引入什么第三方依赖&#xff1f;需要提供什么内容&#xff1f;flink是如何将job提交到k8s上的&#xff1f;经过了什么样的流程&#xff0c;内部有…

React Native 项目 Error: EMFILE: too many open files, watch

硬件&#xff1a;MacBook Pro (Retina, 13-inch, Mid 2014) OS版本&#xff1a;MacOS BigSur 11.7.10 (20G1427) 更新: 删除modules的方法会有反弹&#xff0c;最后还是手动安装了预编译版本的watchman。 React Native 项目运行npm run web&#xff0c;出现如下错误&#xff1a…

51单片机——定时器中断(重点)

STC89C5X含有3个定时器&#xff1a;定时器0、定时器1、定时器2 注意&#xff1a;51系列单片机一定有基本的2个定时器&#xff08;定时器0和定时器1&#xff09;&#xff0c;但不全有3个中断&#xff0c;需要查看芯片手册&#xff0c;通常我们使用的是基本的2个定时器&#xff…

kubernetes第五天

1.Probe&#xff08;探针&#xff09;之readinessProbe就绪探针&#xff0c;可用性检查 readinessProbe此探针如果检查失败&#xff0c;pod会处于未就绪状态 1.exec方式检查 #通过rc资源创建了三个pod,然后使用services资源&#xff0c;对外提供三个pod的容器的访问入口。 ap…