冲刺蓝桥杯之速通vector！！！！！

知识点

C++的STL提供已经封装好的容器vector，也可叫做可变长的数组，vector底层就是自动扩容的顺序表，其中的增删查改已经封装好

创建

const int N=30;
vector<int> a1;//创建叫a1的空的可变长的数组
vector<int> a2(N);//创建大小为30的可变长的数组，里面每个元素为0
vector<int> a3(N,2);//创建大小30的可变长的数组，里面每个元素为2
vector<int> a4={1,2,3,4,5};//初始化列表的创建方式

以上4种更为常用

<> 里面可以放任意的数据类型，
这就体现模板的作用，也体现了模板的强大之处
这样，vector就可以放所有数据类型，包括STL本身

struct Node{
    int a,b;
    string s;
}
vector<string> a5;//存字符串
vector<Node> a6;//存结构体
vector<vector> <int>a7//创建二维可变长数组
vector<int> a[N];//创建大小为N的可变长数组，也是二维，注意小括号和中括号的区别

增删查改

     size求数组大小
     empty检查数组是否为空，是bool类型的返回值
     begin和end遍历数组
     push_back尾插
     pop_back尾删
     front/back返回头/尾元素
     resize扩容，扩的比原来大，大的部分为0，
                 扩的小的话则删除多余的部分
      clear清空数组

直接上代码 简单易懂 ！！！！！！！！！

#include <iostream>
#include <vector>
using namespace std;
const int N = 5;
vector<int> a(N);
void print()
{
	for (int i = 0;i < a.size();i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	
	for (int i = 1;i < 5;i++)
	{
		a.push_back(i);
	}
	print();
	a.pop_back();
	a.pop_back();
	a.pop_back();
	print();
	int t = a.back();
	cout << t << endl;
	a.resize(3);
	print();
	a.clear();
	if (a.empty())
	{
		cout << "空"<<endl;
	}
	return 0;
}

习题1

常言道：学再久 不如多写题理解得快

询问学号
题目描述

有 $n(n\le 2\times 10^6)$ 名同学陆陆续续进入教室。我们知道每名同学的学号（在 $1$ 到 $10^9$ 之间），按进教室的顺序给出。上课了，老师想知道第 $i$ 个进入教室的同学的学号是什么（最先进入教室的同学 $i=1$），询问次数不超过 $10^5$ 次。

输入格式

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

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

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

输出格式

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

样例输入

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

样例输出

1
8
5

思路：两个vector即可解决

#include <iostream>
#include <vector>
using namespace std;
const int N = 2e6;
int n, m;
vector<int> q(N);
vector<int> e(N);
int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
	{
		cin >> q[i];
	}
	for (int i = 1;i <= m;i++)
	{
		cin >> e[i];
		cout << q[e[i]] << endl;
	}
	return 0;
}

习题2

寄包柜
题目描述

超市里有 $n(1\le n\le 10^5)$ 个寄包柜。每个寄包柜格子数量不一，第 $i$ 个寄包柜有 $a_i(1\le a_i\le 10^5)$ 个格子，不过我们并不知道各个 $a_i$ 的值。对于每个寄包柜，格子编号从 1 开始，一直到 $a_i$。现在有 $q(1\le q\le 10^5)$ 次操作：

• 1 i j k：在第 $i$ 个柜子的第 $j$ 个格子存入物品 $k(0\le k\le 10^9)$。当 $k=0$ 时说明清空该格子。
• 2 i j：查询第 $i$ 个柜子的第 $j$ 个格子中的物品是什么，保证查询的柜子有存过东西。

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

输入格式

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

接下来 $q$ 个行，每行有若干个整数，表示一次操作。

输出格式

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

样例输入

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

样例输出

118014
1

思路：有柜子，柜子还带有格子，说明是二维的。柜子用的时候扩容出格子，再加上选择语句可做

#include <iostream>
#include <vector>
using namespace std;
const int N = 100000;
vector<int> e[N];
int n, q;
int num,i,j, k;
int main()
{
	cin >> n >> q;
	while (q--)
	{
		cin >> num >> i >> j;
		if (num == 1)
		{
			cin >> k;
			e[i].resize(j+1);
			e[i][j] = k;
		}
		else
		{
			cout << e[i][j] << endl;
		}

	}
	return 0;
}

习题3

移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

思路：把一个数组分两部分，前面非0，后面是0；用双指针，遍历数组判断条件，交换或指针++

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

习题4：

颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

思路：与上题类似，将数组分3份，最后一份从后面定义，记得循环里面只操作一次，否则i可能越界

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

习题5：

合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

思路：创建新的数组，将两个数组复制给新数组，最后新数组再赋值回去

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