蓝桥备赛（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

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.创建vectorvector<int> a1;//创建了一个名字为a1的可变长数组，里面都是int类型的数据vector<int> a2(N);//创建了一个大小为10的可变长数组vector<int> a3(N, 2);//创建了一个大小为10的可变长数组,并初始化为2vector<int> a4 = { 1,2,3,4 ,5};//使用列表初始化//<> 里面可以放任意的类型，这就是模板的作用，也就是模板的强大之处//这样，vector里面就可以放我们接触过的任意数据类型，甚至是STL本身vector<string> a5;//放字符串vector<node> a6;//放一个结构体vector<vector<int>> a7;//甚至可以放一个自己，当成一个二维数组来使用。并且每一维都是可变的vector<int> a8[N]; // 创造N个vectorreturn 0;
}

4.2 size/empty

1）size ： 返回实际元素的个数 。

2）empty : 返回顺序表是否为空 ， 因此是一个 bool 类型的返回值 。

---> 为空 ： 返回true

---> 不为空：false

#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[i] << " ";}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;elsecout << "非空" << endl;return 0;
}

4.3 begin/end

1)   begin ： 返回起始位置的迭代器（左闭）

2）end： 返回终点位置的下一个位置的迭代器（右开）；

利用迭代器可以访问整个vector , 存在迭代器的容器就可以使用   范围 for 遍历

#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[i] << " ";
//	}
//	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;elsecout << "非空" << 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 3print(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);//扩大 成10a.resize(10);print(a);//缩小成 3a.resize(3);print(a);return 0;
}

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】询问学号 - 洛谷

#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[i];//询问m次，并输出对应的学号 while(m--){int x;cin >> x;cout << a[x] << endl;}return 0;
}

2.2 寄包柜

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

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;const int N = 1e5 + 10;
vector<int> a[N];//创建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[i].size()<= j){//扩容 a[i].resize(j + 1);		}a[i][j] = k;}else//查询{cout << a[i][j] << endl;} }return 0;
}

2.3 移动零

283. 移动零 - 力扣（LeetCode）

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

 

2.4 颜色分类

75. 颜色分类 - 力扣（LeetCode）

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

2.5 合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）

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[cur1] <= nums2[cur2])tmp[cur++] = nums1[cur1++];elsetmp[cur++] = nums2[cur2++];}//此时可能还存在一个数组没有扫描完while(cur1 < m){tmp[cur++] = nums1[cur1++];}while(cur2 < n){tmp[cur++] = nums2[cur2++];}//拷贝回原数组for(int i = 0;i< n + m ; i++){nums1[i] = tmp[i];}}
};

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[cur1] > nums2[cur2])nums1[cur--] = nums1[cur1--];elsenums1[cur--] = nums2[cur2--];}while(cur2>=0){nums1[cur--] = nums2[cur2--];}} 
};

三 、拓展ACM模式 VS 核心代码模式

3.1 ACM 模式

ACM 模式⼀般是竞赛和笔试面试常用的模式，就是只给你⼀个题目描述，外加输入样例和输出样例， 不会给你任何的代码。此时，选手或者应聘者需要根据题目要求，自己完成如下任务：

 

 例如：登录—专业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 核心代码模式

核⼼代码模式仅仅甩给你⼀个函数 ，我们仅需完成这个函数的功能即可。在你完成这个函数之后，后台会调用你所写的函数，进行测试。

因此，这种情况下，我们只需完成核心的函数接口，无需考虑数据的输入和输出。