文章目录
知识点
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 ≤ 2 × 1 0 6 ) n(n \le 2 \times 10^6) n(n≤2×106) 名同学陆陆续续进入教室。我们知道每名同学的学号（在 1 1 1 到 1 0 9 10^9 109 之间），按进教室的顺序给出。上课了，老师想知道第 i i i 个进入教室的同学的学号是什么（最先进入教室的同学 i = 1 i=1 i=1），询问次数不超过 1 0 5 10^5 105 次。
输入格式
第一行 2 2 2 个整数 n n n 和 m m m，表示学生个数和询问次数。
第二行 n n n 个整数，表示按顺序进入教室的学号。
第三行 m m m 个整数，表示询问第几个进入教室的同学。
输出格式
输出 m 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 ≤ n ≤ 1 0 5 ) n(1\le n\le10^5) n(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一，第 i i i 个寄包柜有 a i ( 1 ≤ a i ≤ 1 0 5 ) a_i(1\le a_i\le10^5) ai(1≤ai≤105) 个格子，不过我们并不知道各个 a i a_i ai 的值。对于每个寄包柜，格子编号从 1 开始，一直到 a i a_i ai。现在有 q ( 1 ≤ q ≤ 1 0 5 ) q(1 \le q\le10^5) q(1≤q≤105) 次操作：
1 i j k：在第 i i i 个柜子的第 j j j 个格子存入物品 k ( 0 ≤ k ≤ 1 0 9 ) k(0\le k\le 10^9) k(0≤k≤109)。当 k = 0 k=0 k=0 时说明清空该格子。2 i j：查询第 i i i 个柜子的第 j j j 个格子中的物品是什么，保证查询的柜子有存过东西。
已知超市里共计不会超过 1 0 7 10^7 107 个寄包格子， a i a_i ai 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。
输入格式
第一行 2 个整数 n n n 和 q q q，寄包柜个数和询问次数。
接下来 q 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];
}
}
};