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

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 10;
8. struct node
9. {
10.         int data;
11.         node* next;
12. };
14. int main()
15. {
16.         //1.创建vector
17.         vector<int> a1;//创建了一个名字为a1的可变长数组，里面都是int类型的数据
18.         vector<int> a2(N);//创建了一个大小为10的可变长数组
19.         vector<int> a3(N, 2);//创建了一个大小为10的可变长数组,并初始化为2
20.         vector<int> a4 = { 1,2,3,4 ,5};//使用列表初始化
22.         //<> 里面可以放任意的类型，这就是模板的作用，也就是模板的强大之处
23.         //这样，vector里面就可以放我们接触过的任意数据类型，甚至是STL本身
25.         vector<string> a5;//放字符串
27.         vector<node> a6;//放一个结构体
29.         vector<vector<int>> a7;//甚至可以放一个自己，当成一个二维数组来使用。并且每一维都是可变的
31.         vector<int> a8[N]; // 创造N个vector
32.         return 0;
33. }

复制代码

4.2 size/empty

   1）size ： 返回实际元素的个数 。
  2）empty : 返回顺序表是否为空 ， 因此是一个 bool 范例的返回值 。
  ---> 为空 ： 返回true
  ---> 不为空：false
  

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 10;
8. void print(vector<int>& a)
9. {
10.         for (int i = 0; i < a.size(); i++)
11.         {
12.                 cout << a[i] << " ";
13.         }
14.         cout << endl;
15. }
17. int main()
18. {
19.         vector<int> a1;
20.         vector<int> a2(N);
21.         vector<int> a3 = { 1,2,3,4,5 };
23.         print(a1);
24.         print(a2);
25.         print(a3);
27.         if (a1.empty())
28.                 cout << "空" << endl;
29.         else
30.                 cout << "非空" << endl;
31.         return 0;
32. }

复制代码

4.3 begin/end

   1)   begin ： 返回起始位置的迭代器（左闭）
  2）end： 返回终点位置的下一个位置的迭代器（右开）；
  使用迭代器可以访问整个vector , 存在迭代器的容器就可以使用   范围 for 遍历
  

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 10;
8. //利用迭代器来遍历
9. void print(vector<int>& a)
10. {
11.         for (auto it = a.begin(); it < a.end(); it++)
12.         {
13.                 cout << *it << " ";
14.         }
15.         cout << endl;
16. }
18. //利用size 来遍历
19. //void print(vector<int>& a)
20. //{
21. //        for (int i = 0; i < a.size(); i++)
22. //        {
23. //                cout << a[i] << " ";
24. //        }
25. //        cout << endl;
26. //}
28. int main()
29. {
30.         vector<int> a1;
31.         vector<int> a2(N);
32.         vector<int> a3(N,1);
34.         print(a1);
35.         print(a2);
36.         print(a3);
38.         if (a1.empty())
39.                 cout << "空" << endl;
40.         else
41.                 cout << "非空" << endl;
42.         return 0;
43. }

复制代码

4.4 push_back / pop_back

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

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 10;
8. void print(vector<int>& a)
9. {
10.         for (auto it = a.begin(); it < a.end(); it++)
11.         {
12.                 cout << *it ;
13.         }
14.         cout << endl;
15. }
17. int main()
18. {
19.         vector<int> a = { 1,2,3 };
20.         // 1 2 3
21.         print(a);
22.         //尾插
23.         a.push_back(4);
24.         a.push_back(5);
25.         a.push_back(6);
26.         print(a);
28.         //尾删
29.         a.pop_back();
30.         a.pop_back();
31.         a.pop_back();
32.         print(a);
33.         return 0;
34. }

复制代码

4.5 front / back

   1） front : 返回首元素
  2）back ： 返回尾元素
  时间复杂度：O（1）

1.         cout << a.front() << endl;
2.         cout << a.back() << endl;

复制代码

4.6 resize

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

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 10;
8. void print(vector<int>& a)
9. {
10.         for (auto it = a.begin(); it < a.end(); it++)
11.         {
12.                 cout << *it ;
13.         }
14.         cout << endl;
15. }
17. int main()
18. {
19.         vector<int> a(5, 1);
20.         print(a);
22.         //扩大 成10
23.         a.resize(10);
24.         print(a);
26.         //缩小成 3
27.         a.resize(3);
28.         print(a);
29.         return 0;
30. }

复制代码

4.7 clear

   清空vector
  底层实现的时间 ， 会遍历整个数组 ， 一个一个的删除元素 ， 因此时间复杂度O（N）

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 10;
8. void print(vector<int>& a)
9. {
10.         for (auto it = a.begin(); it < a.end(); it++)
11.         {
12.                 cout << *it ;
13.         }
14.         cout << endl;
15. }
17. int main()
18. {
19.         vector<int> a(5, 1);
20.         print(a);
21.         cout << "大小：" << a.size() << endl;
22.         a.clear();
23.         print(a);
24.         cout << "大小：" << a.size() << endl;
25.         return 0;
26. }

复制代码

     vector 内封装的接口其实还有很多，好比：        1）insert：在指定位置插入一个元素；          2）erase：删除指定位置的元素；          但是，其余的接口要么不常用；要么时间复杂度较高，好比 insert 和 erase，算法竞赛中不        能频仍的调用。         另外，在    https://cplusplus.com/   ，可以查阅各种容器中的接口，以及使用方式   
二、算法题

2.1 询问学号

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

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 2e6 + 10;
8. int n ,m;
9. vector<int> a(N);
10. int main()
11. {
12.         cin >> n >> m;
13.         for(int i = 1;i<= n ; i++)
14.                 cin >> a[i];
15.         //询问m次，并输出对应的学号
16.         while(m--)
17.         {
18.                 int x;
19.                 cin >> x;
20.                 cout << a[x] << endl;
21.         }
22.         return 0;
23. }

复制代码

2.2 寄包柜

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

1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. using namespace std;
6. const int N = 1e5 + 10;
7. vector<int> a[N];//创建N个柜子
8. int n , q;
9. int main()
10. {
11.         cin >> n >> q;
12.         while(q--)
13.         {
14.                 int op, i , j , k;
15.                 cin >> op >> i >> j;
16.                
17.                 if(op == 1)//存
18.                 {
19.                         cin >> k;
20.                         if(a[i].size()<= j)
21.                         {
22.                                 //扩容
23.                                 a[i].resize(j + 1);               
24.                         }
25.                         a[i][j] = k;
26.                 }
27.                 else//查询
28.                 {
29.                         cout << a[i][j] << endl;
30.                 }
31.         }
32.         return 0;
33. }

复制代码

2.3 移动零

283. 移动零 - 力扣（LeetCode）

1. class Solution {
2. public:
3.     void moveZeroes(vector<int>& nums) {
4.         int cur = 0;
5.         for(int i = 0;i < nums.size();i++)
6.         {
7.             if(nums[i] != 0)
8.                 swap(nums[cur++],nums[i]);
9.         }
10.     }
11. };

复制代码

 
2.4 颜色分类

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

1. class Solution {
2. public:
3.     void sortColors(vector<int>& nums) {
4.         int left = 0;
5.         int right = nums.size()-1;
6.         int i = 0;
7.         while(i <= right)
8.         {
9.             if(nums[i] == 0)
10.                 swap(nums[i++],nums[left++]);
11.             else if(nums[i] == 1 )
12.                 i++;
13.             else
14.                 swap(nums[i],nums[right--]);
15.         }
17.     }
18. };

复制代码

2.5 合并两个有序数组

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

1. class Solution {
2. public:
3.     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4.         //解法一：利用辅助数组
5.         vector<int> tmp(m + n);
6.         int cur = 0 , cur1 = 0, cur2 = 0;
7.         while(cur1 < m && cur2 < n)
8.         {
9.             if(nums1[cur1] <= nums2[cur2])
10.                 tmp[cur++] = nums1[cur1++];
11.             else
12.                 tmp[cur++] = nums2[cur2++];
13.         }
14.         //此时可能还存在一个数组没有扫描完
15.         while(cur1 < m)
16.         {
17.              tmp[cur++] = nums1[cur1++];
18.         }
19.         while(cur2 < n)
20.         {
21.             tmp[cur++] = nums2[cur2++];
22.         }
23.         //拷贝回原数组
24.         for(int i = 0;i< n + m ; i++)
25.         {
26.             nums1[i] = tmp[i];
27.         }
28.     }
29. };

复制代码

1. class Solution {
2. public:
3.     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4.         int cur1= m-1,cur2 = n-1, cur = m + n -1;
5.         while(cur1>= 0&& cur2 >= 0)
6.         {
7.             if(nums1[cur1] > nums2[cur2])
8.                 nums1[cur--] = nums1[cur1--];
9.             else
10.                 nums1[cur--] = nums2[cur2--];
11.         }
12.         while(cur2>=0)
13.         {
14.             nums1[cur--] = nums2[cur2--];
15.         }
16.     }
17. };

复制代码

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

3.1 ACM 模式

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

 
 比方：登录—专业IT笔试口试备考平台_牛客网

1. #include <stdio.h> // ⾃⼰写头⽂件
3. // ⾃⼰设计函数接⼝
4. int add(int a, int b)
5. {
6.      return a + b;
7. }
9. int main() // ⾃⼰写主函数
10. {
11. int a = 0, b = 0; // ⾃⼰定义程序所需的变量或者容器（数组）
13. scanf("%d %d", &a, &b); // ⾃⼰处理数据的输⼊
15. int c = add(a, b); // ⾃⼰设计数据的处理逻辑，以及函数的接⼝
16. //（这⾥为了⽅便演⽰，因此⽤了函数，其实我们⼤可不必使⽤函数）
18. printf("%d\n", c); // ⾃⼰处理数据的打印
20. return 0;
21. }

复制代码

3.2 焦点代码模式

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