头文件
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <functional>
#include <queue>
using namespace std;
常用函数
位运算
-
左移。将二进制左移，右边补0
-
1 << N
相当于
2N
2^N
2
N
-
-
异或。位不同为1，位相同为0。
-
a ^ b ^ c = a ^ c ^ b
：交换律 -
x ^ 0 = x
：任何数和0异或为其本身 -
x ^ x = 0
：相同的数异或为0
-
快速排序
sort(v.begin(),v.end(),cmp)
-
v是迭代器，如果只想将一部分排序，可以使用类似
sort(v,v+3)
-
cmp为比较函数，默认是升序排序，也可以重载进行自定义。
return true
时x排在y前面。
bool cmp(const int& x, const int& y)
{
return x > y;
}
int main()
{
vector<int> vec{ 1,3,2 };
sort(vec.begin(), vec.end(), cmp);
cout << vec[0] << " " << vec[1] << " " << vec[2];//3 2 1
return 0;
}
小贴士
-
'c'-'a'
和
'7'-'0'
用来表示字符的次序 - 线性时间复杂度遍历两次三次都没关系，所以可以第一次收集频率，第二次收集位置等等。
Vector
迭代器，可以充当动态数组
#include <vector>
vector<char> s;
基本操作
初始化
vector<char> s1(3,'a');//['a','a','a']
vector<char> s2{ 'a','b','c' };//['a','b','c']
vector<char> s3(3);//['\0','\0','\0']
遍历
for(int i=0; i<s.size() ;i++)
{
char c = (*it);
}
vector<char>::iterator it;
for (it = s.begin(); it != s.end(); it++)
{
char c = (*it);
}
元素编辑
int l=s.size();//返回元素个数
char c=s[2];//类似数组的存取方法
s.push_back('A');//在尾部增加元素
s.pop_back();//删除尾部元素
Map
散列表。map由红黑树构建，自动会排序键，适合排序题，unordered则适合查询题，省去排序时间。
#include <map>
map<string,int> m;
unordered_map<int,int> mm;
基本操作
初始化
vector<char> s1(3,'a');//['a','a','a']
vector<char> s2{ 'a','b','c' };//['a','b','c']
vector<char> s3(3);//['\0','\0','\0']
遍历
map<string,int>::iterator it;
for(it = m.begin(); it!=m.end(); ++it)
{
cout<< it->first << " " << it->second << endl;
}
元素编辑
int l=m.size();//返回元素个数
m["a"]=1;//如果存在，则赋值；如果不存在，则会自动增加键值对。
m.erase("a");//删除该键
if(m.count("a"))//count只会是0（不存在）或1（存在），因为键不会重复
递归
将问题分解为越来越小的子问题，调用递归函数递归地解决。对于数学问题通常要写出递归式
基础案例
阶乘
f
(
n
)
=
{
1
n
=
1
n
⋅
f
(
n
−
1
)
n
>
1
f(n)=\left \{ \begin{matrix}1&n=1\\n\cdot f(n-1)&n>1\end{matrix} \right.
f
(
n
)
=
{
1
n
⋅
f
(
n
−
1
)
n
=
1
n
>
1
- 递归出口：n=1 时，f=1
- 递归传递：返回参数 n 的值
- 单次递归内的过程：用 n 乘以“递归传递”的返回值
int fact(int n)
{
if (n <= 1) return 1;
return n * fact(n - 1);
}
两两交换链表节点
-
递归出口：
head
或
head->next
为空指针 - 递归传递：返回交换后的链表头指针
-
单次递归内的过程：先将
head
指向“递归传递”的返回值，再将
head->next
指回
head
ListNode* swapPairs(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* next = head->next;
head->next = swapPairs(next->next);
next->next = head;
return next;
}