算法笔记
10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；
10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
数据结构和容器
基本类型：
int,long long,short.unsignes.__int128,float,double,long double,char,string,void,bool,const,register,static,auto,struct,union,*,[]unsigned int 0～4294967295
int 2147483648～2147483647
unsigned long 0～4294967295
long 2147483648～2147483647
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：1844674407370955161
__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615
浮点数相同差值：1e-5
list<MM>::iterator iter = find_if(info.begin(), info.end(),
[=](const MM& object) {return object.getName() == name; });
数组
1.189. 轮转数组 - 力扣（Leetcode）数组逆转
2.66. 加一 - 力扣（Leetcode）数组计算数字加减
链表
-
跳表，只用于数据有序的情况，取代平衡树和二分查找
升维，增加多层引索，查询时间复杂度log(n)
-
逆转链表，把每个节点指向前一个即可
-
链表题可以经常设个空指针作为头结点
常用工具
#define INF 0X3f3f3f3f //表示最大整数
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
//cin,cout和printf,scanf拆分
std::ios::sync_with_stdio(false)
//解除cin和cout的绑定，每次要自己刷新endl或flush
cin.tie(nullptr),cout.tie(nullptr)
//循环宏定义
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
最大公因数/公约数
实践应用：https://leetcode.cn/problems/check-if-it-is-a-good-array/
int gcd(int a,int b)
{
int t=0;
while(b!=0)
{
t=a%b;
a=b;
b=t;
}
return a;
}
格雷码
保留最高位，其余位与其高一位异或，实现信号的稳定，每次数值加一时只变化一位数
int a; int b=a^(a>>1);
寻找质数
这里使用埃氏筛法来标记，一般只是适合1e6的数据范围内
vector<bool> vis(n, false);
vector[1] = true;
for(int i = 2; i < n; ++i){
if(!vis[i]){
for(int j = i + i; j < n; j += i){
vis[j] = true;
}
}
}
快速幂
//求a的b次方，一般会使用double ans = pow(a,b)
int getPow(int a, int b){
int ans = 1;
int base = a;
while(b){
if(b&1) ans *= base;
b >>= 1;
base *= base;
}
return ans;
}
二分
int l = 0, r = 1e9+100000;
while(l < r){
int mid = (l+r+1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
有权有向图找路径
- dijkstra算法:贪心,每次找出离起点最近且没有走过的点,更新各点到起点的距离,总共找节点个数次
#define maxn 100001
int dis[maxn], vis[maxn];
int n, m;
vector<vector<pair<int,int>> > adj;
map<int, int>candy;
struct node {
int dis, u;
bool operator>(const node& a) const { return dis > a.dis; }
};
priority_queue<node, vector<node>, greater<node> > q;
void dijkstra(int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0;
q.push({ 0, s }); //起点入栈
while (!q.empty()) {
int u = q.top().u; //从当前距离最短的点去寻找
q.pop();
if (vis[u]) continue; //如果当前点已经走过了,就跳过
vis[u] = 1; //标记当前点走过
for (auto v : adj[u]) { //遍历所有点
int t=v.first, w = v.second;
if (dis[t] > dis[u] + w+candy[u]) { //如果从当前点走的距离小于原先距离
dis[t] = dis[u] + w+candy[u]; //更新最短距离
q.push({ dis[t], t }); //更新后的点入栈
}
}
}
}
int main() {
cin >> n >> m;
adj.resize(n + 1);
for (int i = 0; i < n; i++)
{
int can;
cin >> can;
candy[i + 1] = can;
}
for (int i = 1; i <= m; ++i) {
int u, v,w;
cin >> u >> v>>w;
adj[u].push_back({ v,w });
}
dijkstra(1);
cout << dis[n]+candy[n];
return 0;
}
最小生成树
- kruskal算法(无向图):将所有边按权值从大到小排序,通过找公共祖先判断是否回环,回环不入列
双指针
同一起点快慢指针，头尾双指针
1、11. 盛最多水的容器 - 力扣（Leetcode）左右夹逼
2、15. 三数之和 - 力扣（Leetcode）左右夹逼
3.Linked List Cycle II - LeetCode快慢指针，为什么快指针是两倍，如果以慢指针角度看，快指针以一格的速度逐步向前推进
4.Reverse Nodes in k-Group - LeetCode链表题，n个指针
单调容器
1.84. 柱状图中最大的矩形 - 力扣（Leetcode）
贪心
一般可以用邻项交换的方式来判断是否可以贪心，通过公式判断交换后是否能达到目的
也可以通过优先队列进行后悔操作，在相同占用下，用价值大的替换价值小的
移动窗口
1、1703. 得到连续 K 个 1 的最少相邻交换次数 - 力扣（Leetcode）综合
DP动态规划
1、70. 爬楼梯 - 力扣（Leetcode）简单找规律
查并集
1、1971. 寻找图中是否存在路径 - 力扣（Leetcode）寻路
int n = 1005; // 节点数量3 到 1000
int father[1005];
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
// 并查集里寻根的过程
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return ;
father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
三进制
for (i = 0; i < baseCostsSize; i++) {
for (j = 0; j < n; j++) {
cost = baseCosts[i];
for (k = 0, t = j; k < toppingCostsSize; k++) {
cost += (t % 3) * toppingCosts[k];
t /= 3;
}
if ((abs(cost - target) < abs(ans - target)) || ((abs(cost - target) == abs(ans - target)) && (cost < ans)))
ans = cost;
}
}
回溯
搜索
深度优先