T1 时间复杂度

T2 数据结构-vector动态数组

vector 是一种存储数据的容器

vector的创建：

vector<类型> 名字;
vector<int> v; // 创建一个int类型一维的空动态数组
vector<int> v(n,x); // 创建一个int类型一维动态数组，初始长度n，值为x。
vector<int> v[N]; // 创建一个int类型二维的动态数组，其中一维长度为N，二维长度可变
vector<vector<int>> v(n,vector<int>(m,x)) // 创建一个int类型n行m列的二维动态数组，初始值为x

vector的常用操作函数：

vector<int> v;
v.push_back(x); // 把元素x添加到末尾
v.pop_back(); // 把末尾元素删除
v.size(); // 返回长度
v[i]; // 获取下标为 i 的元素
v.front(); // 获取首位元素，也可以使用下标 v[0]
v.back(); // 获取末尾元素，也可以使用下标 v[v.size()-1]
v.clear(); // 清空容器
v.begin(); // 返回一个迭代器，指向容器的第一个元素
v.end(); // 返回一个迭代器，指向容器的最后一个元素的后一位
v.erase(v.begin()+1, v.begin()+4); // 删除容器中下标 1~4 的元素，删除的时间复杂度是O(n)

vector的循环遍历与输入输出：

(1) 往空数组添加元素
vector<int> v;
for (int i = 0; i < n; i++)
{
  int x; cin >> x;
  v.push_back(x); // 通过push_back往末尾添加n个数
}

(2) 提前声明数组大小，可以类似普通数组用下标输入
vector<int> v(n+1); // n+1是为了从1号下标开始存数据
for (int i = 1; i <= n; i++) cin >> v[i];

(3) 循环输出vector的元素
for (int i = 0; i < v.size(); i++) cout << v[i];

(4) 枚举型遍历
for (auto it : v) cout << it;

(5) 排序vector
sort(v.begin(), v.end())

(6) 对vector排序并去重
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // unique函数必须先排序才能起到去重效果

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;//创建一个int类型二维的动态数组，其中一维长度为N，二维长度可变
vector<int> v[N];
int main()
{
	int n,m;
	cin>> n >> m;
	while(m--)
	{
		int x,y;
		cin>> x >> y;// 向第x个数组添加元素y
		v[x].push_back(y);// 将元素y添加到第x个数组的末尾
	}// 遍历每个数组，输出结果
	for(int i = 1;i <= n;i++)
	{
		cout<< v[i].size() << " ";// 输出第i个数组的元素个数
		sort(v[i].begin(),v[i].end());// 对第i个数组的元素进行排序
		for(int j = 0;j < v[i].size();j++)
		{ // 输出排序后的元素
			cout<< v[i][j] << " ";
		} 
		cout<< endl;// 换行继续处理下一个数组
	}
	return 0;
}

T3 #145. 数据结构-stack栈

栈（Stack）是一种基于 后进先出(LIFO) 原则的数据结构，它是一种线性表。栈具有两个主要操作：压入 (Push) 和弹出 (Pop)。

#include<stack>
stack<int> stk;  // 创建int类型栈，名字为stk
stk.push(x)      // 把x压栈
stk.pop()        // 弹出栈顶元素
stk.top()        // 查看栈顶元素
stk.size()       // 返回栈内元素个数
stk.empty()      // 返回栈是否为空

#include<bits/stdc++.h>
using namespace std;
stack<int> t;
int main(){
    int m;
    cin>> m;// 读取操作次数
    while(m--){
        string j;
        cin>> j;
        if(j == "push")
		{
            int x;
            cin>> x;// 读取要压入栈的元素
            t.push(x);// 将元素压入栈顶
        } 
        else if(j == "pop")
		{
            t.pop();// 弹出栈顶元素
        }
        else if(j == "empty"){// 判断栈是否为空，判断后输出"YES"或"NO"
            cout<<(t.empty()?"YES":"NO")<< endl;
        } //三元运算符
        else if(j == "query"){
            cout<< t.top()<< endl;// 输出栈顶元素的值
        }
    }
    return 0;
}

T4 数据结构-queue队列

队列（Queue）是一种常见的数据结构，它遵循先进先出（FIFO）的原则。队列有两个主要的操作：

入队：向队尾插入新元素。 出队：从队头移除元素。

除了这两个基本操作外，队列通常还包括以下操作：

队列判空：检查队列是否为空。

队列长度：获取队列中元素的个数。

获取队头元素：获取队头元素的值，但不移除它。

队列常用于模拟排队、任务调度等场景。在后续算法学习中，BFS广度优先搜索也要借助队列来实现。

STL 队列用法

#include<queue>
queue<int> q;
q.push(x);  // 队尾插入x
q.pop();    // 弹出队头
q.front();  // 查看队头
q.back();   // 查看队尾
q.size();   // 查看q元素个数
q.empty();  // 查看q是否为空

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>> n >> m;// 输入总人数n和报数间隔m
queue<int> q;// 使用队列存储当前圈中的所有人
for(int i = 1;i <= n;i++) q.push(i);// 初始化队列，将编号为1到n的人依次入队	
int cnt = 0;// 报数计数器，记录当前报数的值
while(q.size())// 当队列不为空时，继续模拟出圈过程
{
	cnt++;// 报数递增
	int c = q.front();// 取出队首元素（当前报数的人）
	q.pop();// 队首元素出队
	if(cnt % m == 0)// 判断当前报数是否为m的倍数，如果是，则当前人出圈（不重新入队）
	{
		cout<< c << " ";// 输出出圈人的编号
	}
	else// 如果不是，则当前人重新入队尾，继续参与报数
	{
		q.push(c);
	}		
}
return 0;
}

T5 数据结构-set和unordered_set集合

set 是按照特定顺序存储唯一元素的容器，即自带排序和去重。它非常适合处理需要同时兼顾查找、插入和删除的情况。元素放入 set 后不支持修改，但可以删除。

和数学中的集合相似，set 中不会出现值相同的元素，如果需要有相同元素，则可以使用 multiset，multiset 除了此特性之外，其他地方与 set 没啥区别，所以不再单独介绍。

创建一个set：

set<类型> 名字;

set的常用操作方法：

s.insert(x) 当容器中没有等价元素的时候，将元素 x 插入到 set 中。
s.erase(x) 删除值为 x 的所有元素，返回删除元素的个数。
s.clear() 清空 set。
s.count(x) 返回 set 内键为 x 的元素数量。
s.find(x) 在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end()。
s.empty() 返回容器是否为空。
s.size() 返回容器内元素个数。

输出方法：

set<int> s;
s.insert(1);
s.insert(3);
s.insert(6);
for (auto it:s)
  cout << it << " ";

for (auto it = s.begin(); it!=s.end(); it++)
	cout << *it << " ";

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int N;// 输入整数的数量
    cin >> N;
    set<int> q;// 使用set存储整数，自动去重并排序  
    for (int i = 0; i < N; i++) 
	{ // 读取N个整数，并插入到set中
        int num;
        cin >> num;
        q.insert(num); // set自动去重，重复元素只保留一个
    } 
    }
    cout << q.size() << endl; // 输出去重后的元素个数 
    for (auto it = q.begin(); it != q.end(); it++) // 遍历set中的元素
	{
        cout << *it;// 输出当前元素
        if (next(it) != q.end()) 
		{  // 在元素之间输出空格，但最后一个元素后不输出空格
            cout << " ";
        }
    }
    cout << endl;// 换行
    return 0;
}

T6 数据结构-map和unordered_map哈希表

map 是有序键值对容器（自动按照键排序），它的元素的键是唯一的。搜索、移除和插入操作均拥有对数复杂度。可以把map理解成高级的桶数组，桶数组只能实现 int --> int 的映射，map则不受限制。

创建一个map：

map<类型, 类型> 名字;

比如要存储学生的名字和对应成绩，可以创建map<string, int> score;

map的常用操作方法：

map<int,int> mp;
mp[3] = 5; // 通过赋值创建一个键值对映射
mp[4] = 2;
mp[2] = 7;
mp.erase(4); // 删除{4，2}这个键值对
cout << mp.count(2); // 输出1，表示2这个键存在
cout << mp.count(5); // 输出0，表示5这个键不存在

// 枚举型遍历访问map的所有键值对
for (auto it : mp) 
{
  cout << it.first << " " << it.second << endl;
}

unordered_map 【哈希表】的基础用法和map一样，只不过它不会自动排序，所以访问速度更快。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n;
    cin>> n;// 输入整数的数量
    map<ll,int> j;// 使用map统计每个整数出现的次数
    for(int i = 0;i < n;i++)// 读取n个整数，并统计每个整数的出现次数
	{
        ll x;
        cin>> x;
        j[x]++;// 对应整数的计数器上加1
       
    }
    for (auto it : j)// 遍历map，按顺序输出每个整数和这个数的出现次数 
	{
		cout << it.first << " " << it.second << endl;
	}// it.first 是整数的值，it.second 是该整数出现的次数
    return 0;