四川省广安建设局网站,一个好网站,做视频分享网站的参考书,百度推广后台登录页面文章目录 1.1 排序STL sort函数快速排序算法模板归并排序算法模板 1.2 二分整数二分算法模板浮点数二分算法模板 1.3 高精度高精度加法高精度减法高精度乘低精度高精度除以低精度 1.4 前缀和与差分**一维前缀和****二维前缀和****一维差分****二维差分** 之前整理了好多算法模板… 文章目录 1.1 排序STL sort函数快速排序算法模板归并排序算法模板 1.2 二分整数二分算法模板浮点数二分算法模板 1.3 高精度高精度加法高精度减法高精度乘低精度高精度除以低精度 1.4 前缀和与差分**一维前缀和****二维前缀和****一维差分****二维差分** 之前整理了好多算法模板打算整理一下。 刚好可以打印出来带板子比赛[](▽)*
1.1 排序
STL sort函数
sort(arr, arr n); // 对 arr[0] 到 arr[n-1] 排序默认升序
sort(arr, arr n, greaterint()); // 降序排序sort(nodes.begin(), nodes.end()); //容器用迭代器排序//cmp函数
bool cmp(int a, int b) {return a b; // 降序a 在 b 前
}
sort(arr, arr n, cmp);//lambda
sort(arr, arr n, [](int a, int b) {return a b; // 降序
});快速排序算法模板
void quick_sort(int q[], int l, int r)
{if (l r) return;int i l - 1, j r 1, x q[l r 1];while (i j){do i ; while (q[i] x);do j -- ; while (q[j] x);if (i j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j 1, r);
}
归并排序算法模板
void merge_sort(int q[], int l, int r)
{if (l r) return;int mid l r 1;merge_sort(q, l, mid);merge_sort(q, mid 1, r);int k 0, i l, j mid 1;while (i mid j r)if (q[i] q[j]) tmp[k ] q[i ];else tmp[k ] q[j ];while (i mid) tmp[k ] q[i ];while (j r) tmp[k ] q[j ];for (i l, j 0; i r; i , j ) q[i] tmp[j];
}
1.2 二分
整数二分算法模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 右偏
int bsearch_1(int l, int r)
{while (l r){int mid l r 1;if (check(mid)) r mid; // check()判断mid是否满足性质else l mid 1;}return l;
}
// 左偏
int bsearch_2(int l, int r)
{while (l r){int mid l r 1 1;if (check(mid)) l mid;else r mid - 1;}return l;
}
浮点数二分算法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r)
{const double eps 1e-6; // eps 表示精度取决于题目对精度的要求while (r - l eps){double mid (l r) / 2;if (check(mid)) r mid;else l mid;}return l;
}
1.3 高精度
高精度加法
// C A B, A 0, B 0
vectorint add(vectorint A, vectorint B)
{if (A.size() B.size()) return add(B, A);vectorint C;int t 0;for (int i 0; i A.size(); i ){t A[i];if (i B.size()) t B[i];C.push_back(t % 10);t / 10;}if (t) C.push_back(t);return C;
}
高精度减法
// C A - B, 满足A B, A 0, B 0
vectorint sub(vectorint A, vectorint B)
{vectorint C;for (int i 0, t 0; i A.size(); i ){t A[i] - t;if (i B.size()) t - B[i];C.push_back((t 10) % 10);if (t 0) t 1;else t 0;}while (C.size() 1 C.back() 0) C.pop_back();return C;
}
高精度乘低精度
// C A * b, A 0, b 0
vectorint mul(vectorint A, int b)
{vectorint C;int t 0;for (int i 0; i A.size() || t; i ){if (i A.size()) t A[i] * b;C.push_back(t % 10);t / 10;}while (C.size() 1 C.back() 0) C.pop_back();return C;
}
高精度除以低精度
// A / b C ... r, A 0, b 0
vectorint div(vectorint A, int b, int r)
{vectorint C;r 0;for (int i A.size() - 1; i 0; i -- ){r r * 10 A[i];C.push_back(r / b);r % b;}reverse(C.begin(), C.end());while (C.size() 1 C.back() 0) C.pop_back();return C;
}
1.4 前缀和与差分
前缀和用于查询为主适合固定子区间的快速统计。差分用于修改为主适合频繁的区间修改操作。二维场景扩展了思路可以解决棋盘、地图、图像等多维数据的问题是动态规划和模拟算法中的重要工具。
一维前缀和
核心思想快速求任意子区间的元素和。 应用场景 求区间和如数组中某段区间的累积和快速查询多个子区间。特定条件下的子数组统计如统计满足某和的子数组个数、等差数列的前缀统计等。优化暴力循环在滑动窗口、双指针结合场景下减少重复计算。动态和的判断如 LeetCode 560 的“和为 K 的子数组”。
S[i] a[1] a[2] ... a[i]
a[l] ... a[r] S[r] - S[l - 1]二维前缀和
核心思想快速求任意矩形区域的元素和。 应用场景 矩形区域查询如地图/棋盘中矩形区域的累积值快速实现范围统计。统计二维频率矩阵如统计某字符矩阵内某个字符出现次数。处理图像/像素值矩阵如积分图的计算用于快速处理图像区域的统计。最大子矩阵和如求二维数组的子矩阵的最大和或固定形状的区域统计。
S[i, j] 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角(x2, y2)为右下角的子矩阵的和为
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] S[x1 - 1, y1 - 1]一维差分
核心思想高效处理多次区间修改操作最终还原原数组。 应用场景 区间增减问题如“给区间加上固定值”、“统计区间操作后某值出现的频次”。区间频次统计如单点操作转换为区间统计模拟更新效果。物理量累积模拟如力的分布计算能量在区间上的增减。效率优化从 O(n⋅q)O(n \cdot q) 提升到 O(nq)O(n q)如对一个数组进行大量区间修改的场景。
给区间[l, r]中的每个数加上cB[l] c, B[r 1] - c二维差分
核心思想高效处理多次矩形区域修改操作最终还原 原矩阵。 应用场景 矩形区域增减问题如在二维数组的某矩形区域内统一加减一个数。累计影响模拟如模拟一个范围的热量扩散、光照叠加。频次矩阵构建如对二维频次表进行增量操作快速得到最终统计值。动态二维修改问题如棋盘状态更新积木或区域重叠分析。
给以(x1, y1)为左上角(x2, y2)为右下角的子矩阵中的所有元素加上c
S[x1, y1] c, S[x2 1, y1] - c, S[x1, y2 1] - c, S[x2 1, y2 1] c
