物联网蓝桥备赛（12） - 顺序表和 vector（下）

干翻全岛蛙蛙 发表于 2025-3-9 10:14:01

蓝桥备赛（12）- 顺序表和 vector（下）

目录
一、动态顺序表 - vector
4.1 创造vector
4.2 size/empty
4.3 begin/end
4.4 push_back / pop_back
4.5 front / back
4.6 resize
4.7 clear
二、算法题
2.1 询问学号
2.2 寄包柜
2.3 移动零
2.4 颜色分类
2.5 合并两个有序数组
三、拓展ACM模式 VS 焦点代码模式
3.1 ACM 模式
3.2 焦点代码模式

一、动态顺序表 - vector

https://i-blog.csdnimg.cn/direct/9625f34b459e410a8d8198c971099ac8.png
4.1 创造vector

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 10;

struct node
{
int data;
node* next;
};

int main()
{
//1.创建vector
vector<int> a1;//创建了一个名字为a1的可变长数组，里面都是int类型的数据
vector<int> a2(N);//创建了一个大小为10的可变长数组
vector<int> a3(N, 2);//创建了一个大小为10的可变长数组,并初始化为2
vector<int> a4 = { 1,2,3,4 ,5};//使用列表初始化

//<> 里面可以放任意的类型，这就是模板的作用，也就是模板的强大之处
//这样，vector里面就可以放我们接触过的任意数据类型，甚至是STL本身

vector<string> a5;//放字符串

vector<node> a6;//放一个结构体

vector<vector<int>> a7;//甚至可以放一个自己，当成一个二维数组来使用。并且每一维都是可变的

vector<int> a8; // 创造N个vector
return 0;
}

4.2 size/empty

1）size ：返回实际元素的个数。
2）empty : 返回顺序表是否为空，因此是一个 bool 范例的返回值。
---> 为空：返回true
---> 不为空：false
https://i-blog.csdnimg.cn/direct/a10ebc8141244d3b8a780a1d94802c7f.png
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 10;

void print(vector<int>& a)
{
for (int i = 0; i < a.size(); i++)
{
cout << a << " ";
}
cout << endl;
}

int main()
{
vector<int> a1;
vector<int> a2(N);
vector<int> a3 = { 1,2,3,4,5 };

print(a1);
print(a2);
print(a3);

if (a1.empty())
cout << "空" << endl;
else
cout << "非空" << endl;
return 0;
}
4.3 begin/end

1) begin ：返回起始位置的迭代器（左闭）
2）end：返回终点位置的下一个位置的迭代器（右开）；
使用迭代器可以访问整个vector , 存在迭代器的容器就可以使用范围 for 遍历
https://i-blog.csdnimg.cn/direct/da2230297f2f4d409405974f4fedff4c.png
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 10;

//利用迭代器来遍历
void print(vector<int>& a)
{
for (auto it = a.begin(); it < a.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}

//利用size 来遍历
//void print(vector<int>& a)
//{
// for (int i = 0; i < a.size(); i++)
// {
// cout << a << " ";
// }
// cout << endl;
//}

int main()
{
vector<int> a1;
vector<int> a2(N);
vector<int> a3(N,1);

print(a1);
print(a2);
print(a3);

if (a1.empty())
cout << "空" << endl;
else
cout << "非空" << endl;
return 0;
}
4.4 push_back / pop_back

1) push_back : 尾部添加一个元素
2）pop_back : 尾部删除一个元素
时间复杂度 : O(1)
当然还有 insert 和 erase . 不过由于时间复杂度过高，只管不建议使用；
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 10;

void print(vector<int>& a)
{
for (auto it = a.begin(); it < a.end(); it++)
{
cout << *it ;
}
cout << endl;
}

int main()
{
vector<int> a = { 1,2,3 };
// 1 2 3
print(a);
//尾插
a.push_back(4);
a.push_back(5);
a.push_back(6);
print(a);

//尾删
a.pop_back();
a.pop_back();
a.pop_back();
print(a);
return 0;
}
4.5 front / back

1） front : 返回首元素
2）back ：返回尾元素
时间复杂度：O（1）
cout << a.front() << endl;
cout << a.back() << endl;
4.6 resize

1）修改vector 的巨细
2）如果大于原始的巨细，多出来的位置会补上默认值，一般是0
3）如果小于原始的巨细，相当于把后面的元素全部删掉
时间复杂度：O(n)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 10;

void print(vector<int>& a)
{
for (auto it = a.begin(); it < a.end(); it++)
{
cout << *it ;
}
cout << endl;
}

int main()
{
vector<int> a(5, 1);
print(a);

//扩大成10
a.resize(10);
print(a);

//缩小成 3
a.resize(3);
print(a);
return 0;
}
https://i-blog.csdnimg.cn/direct/75d166aa868a400ba107f9369375412a.png

4.7 clear

清空vector
底层实现的时间，会遍历整个数组，一个一个的删除元素，因此时间复杂度O（N）
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 10;

void print(vector<int>& a)
{
for (auto it = a.begin(); it < a.end(); it++)
{
cout << *it ;
}
cout << endl;
}

int main()
{
vector<int> a(5, 1);
print(a);
cout << "大小：" << a.size() << endl;
a.clear();
print(a);
cout << "大小：" << a.size() << endl;
return 0;
}    vector 内封装的接口其实还有很多，好比：    1）insert：在指定位置插入一个元素；       2）erase：删除指定位置的元素；       但是，其余的接口要么不常用；要么时间复杂度较高，好比 insert 和 erase，算法竞赛中不    能频仍的调用。       另外，在   https://cplusplus.com/ ，可以查阅各种容器中的接口，以及使用方式
二、算法题

2.1 询问学号

P3156 【深基15.例1】询问学号 - 洛谷
https://i-blog.csdnimg.cn/direct/cf1bdc2a62634977b114048fac1c9e17.png
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 2e6 + 10;

int n ,m;
vector<int> a(N);
int main()
{
cin >> n >> m;
for(int i = 1;i<= n ; i++)
cin >> a;
//询问m次，并输出对应的学号
while(m--)
{
int x;
cin >> x;
cout << a << endl;
}
return 0;
}

2.2 寄包柜

P3613 【深基15.例2】寄包柜 - 洛谷
https://i-blog.csdnimg.cn/direct/4d65d832cf2b4a409e20083eea88dd48.png
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
vector<int> a;//创建N个柜子
int n , q;
int main()
{
cin >> n >> q;
while(q--)
{
int op, i , j , k;
cin >> op >> i >> j;

if(op == 1)//存
{
cin >> k;
if(a.size()<= j)
{
//扩容
a.resize(j + 1);
}
a = k;
}
else//查询
{
cout << a << endl;
}
}
return 0;
}
2.3 移动零

283. 移动零 - 力扣（LeetCode）
https://i-blog.csdnimg.cn/direct/f70723af578e431e8d3f783b208692cf.png
class Solution {
public:
void moveZeroes(vector<int>& nums) {
   int cur = 0;
   for(int i = 0;i < nums.size();i++)
   {
         if(nums != 0)
            swap(nums,nums);
   }
}
};
2.4 颜色分类

75. 颜色分类 - 力扣（LeetCode）
https://i-blog.csdnimg.cn/direct/1f26b4625f7c47ad86e80573091ea8ee.png
class Solution {
public:
void sortColors(vector<int>& nums) {
   int left = 0;
   int right = nums.size()-1;
   int i = 0;
   while(i <= right)
   {
         if(nums == 0)
            swap(nums,nums);
         else if(nums == 1 )
            i++;
         else
            swap(nums,nums);
   }

}
};
2.5 合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）
https://i-blog.csdnimg.cn/direct/2660d4957ca04067a90e8147555efbf3.png
https://i-blog.csdnimg.cn/direct/cd4801d8176640efab5236e229f42144.png
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
   //解法一：利用辅助数组
   vector<int> tmp(m + n);
   int cur = 0 , cur1 = 0, cur2 = 0;
   while(cur1 < m && cur2 < n)
   {
         if(nums1 <= nums2)
            tmp = nums1;
         else
            tmp = nums2;
   }
   //此时可能还存在一个数组没有扫描完
   while(cur1 < m)
   {
         tmp = nums1;
   }
   while(cur2 < n)
   {
         tmp = nums2;
   }
   //拷贝回原数组
   for(int i = 0;i< n + m ; i++)
   {
         nums1 = tmp;
   }
}
}; https://i-blog.csdnimg.cn/direct/8f650cf92f5b47339f985575bf3c8440.png
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
   int cur1= m-1,cur2 = n-1, cur = m + n -1;
   while(cur1>= 0&& cur2 >= 0)
   {
         if(nums1 > nums2)
            nums1 = nums1;
         else
            nums1 = nums2;
   }
   while(cur2>=0)
   {
         nums1 = nums2;
   }
}
};

三、拓展ACM模式 VS 焦点代码模式

3.1 ACM 模式

   ACM 模式⼀般是竞赛和笔试口试常用的模式，就是只给你⼀个题目描述，外加输入样例和输出样例，不会给你任何的代码。此时，选手大概应聘者必要根据题目要求，自己完成如下使命： https://i-blog.csdnimg.cn/direct/15d96bf75368410d997b9cdeb09f1792.png

比方：登录—专业IT笔试口试备考平台_牛客网
#include <stdio.h> // ⾃⼰写头⽂件

// ⾃⼰设计函数接⼝
int add(int a, int b)
{
return a + b;
}

int main() // ⾃⼰写主函数
{
int a = 0, b = 0; // ⾃⼰定义程序所需的变量或者容器（数组）

scanf("%d %d", &a, &b); // ⾃⼰处理数据的输⼊

int c = add(a, b); // ⾃⼰设计数据的处理逻辑，以及函数的接⼝
//（这⾥为了⽅便演⽰，因此⽤了函数，其实我们⼤可不必使⽤函数）

printf("%d\n", c); // ⾃⼰处理数据的打印

return 0;
} 3.2 焦点代码模式

   核⼼代码模式仅仅甩给你⼀个函数，我们仅需完成这个函数的功能即可。在你完成这个函数之后，背景会调用你所写的函数，进行测试。    因此，这种情况下，我们只需完成焦点的函数接口，无需思量数据的输入和输出。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

页: [1]

IT评测·应用市场-qidao123.com技术社区's Archiver

蓝桥备赛（12）- 顺序表和 vector（下）