- find the kth smallest element in the (sorted) matrix
- biselect: SELECTION IN X + Y，二维数组的Top K问题
- median of medians
- BFS
- two way BFS
- DFS
- Dijkstra's Algorithm
- heap + bfs / A*
- Bellman Ford
- dp
- Bipartite graph/network 二分图
- 匹配,最大匹配 (maximal matching problem),完全匹配/完备匹配
- 增广路径: 若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边（即已匹配和待匹配的边）在P上交替出现，则称P为相对于M的一条增广路径
- P的路径长度必为奇数,第一条和最后一条边都不属于M
- P经过取反操作可以得到一个更大的匹配M'
- M为G的最大匹配当且仅当不存在相对于M的增广路径
- 利用增广路径求最大匹配(匈牙利算法 Hungary: 求无边权二分图的最大匹配) TODO
- KM算法：带权二分图的最大权完美匹配 TODO
- 增广路径: 若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边（即已匹配和待匹配的边）在P上交替出现，则称P为相对于M的一条增广路径
- leetcode 0886: 就是判断是不是二分图
- 用染色法解决
- 匹配,最大匹配 (maximal matching problem),完全匹配/完备匹配
- 网络流算法
-
coords = set() for left, size in positions: coords.add(left) coords.add(left + size - 1) index = {x: i for i, x in enumerate(sorted(coords))} # position: [(100,100), (200,100)] # index = {100: 0, 199: 1, 200: 2, 299: 3}
- TODO
- TODO
- used in computing shortest distance/path in a grid from S to T
- faster than bfs, use dequeue (double ended queue), each node stores an extra
detour_countvalue (while bfs just needs node's row and column value) - the wanted shortest distance (if found: cur_node == T) is
hamming distance + 2*detour_count, when we move closer to T,detour_countremains same as last node, push thisnext_nodeto dequeue from one side (we getcur_nodealso from this side); when we move further from T,detour_countincreases by 1, and we push thisnext_nodeto dequeue from the other side of dequeue. (basically same as bfs, just uses a dequeue) - related problems: leetcode 0675: Cut Off Trees for Golf Event, code on github
-
-
algorithm Sieve of Eratosthenes is input: an integer n > 1. output: all prime numbers from 2 through n. let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true. for i = 2, 3, 4, ..., not exceeding √n do if A[i] is true for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do A[j] := false return all i such that A[i] is true.
-
- TODO
-
related problems
- Convex hull & different algorithms
- Graham's Scan
- Andrew's Monotone Chain (better I think)
- wiki
- related problems:
- TODO
- 2-sat算法
- my blog: knapsack problems
- 经典背包问题 01背包+完全背包+多重背包
- 二进制分解（多重背包）
-
bool nextPermutation(string& nums) { if (nums.empty()) return false; int i = nums.size() - 1; while (i >= 1 && nums[i] <= nums[i - 1]) i--; if (i == 0) return false; // no next permutation, i.e. already largest int j = nums.size() - 1; while (nums[j] <= nums[i - 1]) j--; swap(nums[i - 1], nums[j]); reverse(nums.begin() + i, nums.end()); return true; }
-
related problems:
-
法2: 适合大组合数 / 大数处理 (更好，更简单，更快)，
但不精确整数能有多不精确
核心就是 取对数进行运算，乘除法转为加减法
对于$C(n, k) = (n!)/((n-k)!)/(k!)$
等价于(这里用浮点数，可能会有精度损失):
如果结果特别大时，一般题目会让你继续用这个数和另外一个很小的数相乘(另外的这个数也用相同底的对数形式表示即可)，所以继续用对数保存(暂时不要算$exp()$); 如果直接需要这个整数结果可以将结果取整$int(x+0.5)$
所以只需要提前算好$log(n!)$就好了，$log(n!)=log(1)+log(2)+...+log(n)$
相关题目：google kickstart round B, 4
- Reservoir sampling
- 有一种算法叫做“Union-Find”？ (原文有错--博主知道了，但好像还没改。。。见第一条评论
id[q]=pID;//这里应该改为id[qID]=pID;) - related problems
-
ref: Kadane's Algorithm
-
O(n)时间计算求最大的子数组元素和
-
拓展：同样求子数组最大元素和，但外加限制和小于k，O(nlog(n))时间解法
- 最近用到的数据被重用的
概率比最早用到的数据大的多
-
最大前缀后缀公共元素长度（实际上是dp问题）
-
// D A B C D A B D E // 0 0 0 0 1 2 3 1 0 int main() { string s = "DABCDABDE"; int n = s.length(); // int len = 0; // int i = 1; // 从第二个字符开始 vector<int> tr(n); for (int len = 0, i = 1; i < n;) { if (s[i] == s[len]) tr[i++] = ++len; else if (len == 0) tr[i++] = 0; else len = tr[len-1]; } }
-
-
匹配过程
-
int main() { string s1 = "ABAABABAC" string s2 = "BABAC"; // ABAA(BABAC) int n1 = s1.length(), n2 = s2.length(); vector<int> tr(n2); for (int len = 0, i = 1; i < n2;) { if (s2[i] == s2[len]) tr[i++] = ++len; else if (len == 0) tr[i++] = 0; else len = tr[len-1]; } // B A B A C // 0 0 1 2 0 for (int i = 0, j = 0; i < n1; ) { // i never decreases while (j < n2 && s1[i] == s2[j]) { ++i; ++j; } if (j == n2) { // found a match // match start at // cout << i - j << endl; // return 0; // or continue matching more // TODO ... // i may decrease ? change tr ? // ... } // not found if (j == 0) ++i; else j = tr[j-1]; } }
-
- 删除单词是另一个单词的前缀 -- 只需要把最后一个节点的isWord改成false
- 除了尾部几个节点没有分支，中间节点有分支 -- 删除到最深的分支节点处
-
naive way
bool cmp(string& a, string& b) { return a + b > b + a; }
-
smarter way?
bool cmp(string& a, string& b) { int blen = b.size(); int alen = a.size(); int i = 0; for (; i < (alen + blen) && b[i%blen] == a[i%alen]; ++i) return a[i%alen] > b[i%blen]; };
- 每次选择最小的元素排好
- 跟玩扑克牌类似，每次插入一个元素到已排序数组合适位置
- 应该比选择排序要快（不用每次遍历所有元素，找到合适位置就停下，而选择排序要遍历所有的才能找到最小元素）
- 尤其对于近乎有序的数组，插入排序更好
- 也是适合对近乎有序的数组排序，但不如插入排序好
- 每次从0下标开始，不断和相邻元素比较并选择是否交换两元素，每次冒泡出一个最大元素
- virtual indexing, partition: leetcode discuss
- 判断是否有环
- 判断开始进入环的节点
- 快慢指针首次相遇了
- 从相遇点再往后的第n个节点与从头往后的第n个节点，两节点相同
- related problems:
- 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边
- 满二叉树：高度为h，由2^h-1个节点构成的二叉树称为满二叉树。
- Preorder, Inorder, and Postorder Iteratively Summarization
- 相当于从左到右遍历，对于二叉搜索树BST，就是从小到大遍历
- 二叉树的中序遍历非递归算法
- 二叉树非递归后序遍历
- 由于镜像二叉树的先序遍历=原二叉树后序遍历，可以先求出镜像先序，最后reverse一下即可。
int n;
vector<int> A;
template <typename T>
void printArr(const vector<T> &arr) {
for (const T &t : arr) cout << t << " ";
cout << endl;
}
int sum(int i) { // A[1] + A[2] + ... + A[i]
int res = 0;
while (i) res += A[i], i -= i & -i;
return res;
}
void add(int i, int k) { // adds k to A[i]
while (i <= n) A[i] += k, i += i & -i;
}
int main(int argc, char const *argv[]) {
cout << "input the number of elements to be added, n: ";
cin >> n;
A.resize(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> A[0];
add(i, A[0]);
}
// printArr(A);
while (1) {
cout << "get sum of first x elements, x: ";
int x;
cin >> x;
if (x > 0 && x <= n)
cout << "sum of first " << x << " elements is " << sum(x) << endl;
else
break;
}
return 0;
}- Segment Tree w/ Lazy Propagation (TODO)
- Segment Tree (Iterative)
- Segment tree Theory and applications
- A Recursive approach to Segment Trees, Range Sum Queries & Lazy Propagation
- 线段树（segment tree），看这一篇就够了
- 线段树小结
计算星期几（基姆拉尔森计算公式）
-
int _day_of_week(int year, int month, int day=1) { if (month == 1 || month == 2) { --year; month += 12; } // 0 -- Sunday 1 -- Monday return (day + 2*month + 3*(month+1)/5 + year + year/4 - year/100 + year/400 + 1) % 7; }
-
相关题目
-
template <typename T> T pow(T x, int n) { T ret = 1; while (n) { if (n & 1) { // 按位与比n%2更快 ret *= x; } x *= x; n >>= 1; } return ret; }
-
// remove sign of operands long div = dividend; long dsr = divisor; div = abs(div); dsr = abs(dsr); long long tmp = 0; long long quotient = 0; // 这里模拟除法运算，二进制的，从第31位一直到第0位 for(int i = 31; i>= 0; --i) { if(tmp + (dsr<<i) <= div) { tmp += dsr << i; quotient |= 1LL << i; } }
- ref: Matrix - By DanAlex
template <typename T, std::size_t R, std::size_t C = R,
std::size_t M = INT32_MAX>
class Matrix {
public:
T m[R][C];
Matrix() { memset(m, 0, sizeof(m)); }
/**
* construct a matrix whose diagonal (fill at most min(R, C) number as x) is
* filled with number x, and the rest filled with 0's
* @param x number to be filled at the diagonal
* @param isMainDiagonal fill main diagonal if true, else fill the
* antidiagonal
*/
Matrix(T x, bool isMainDiagonal = true) : Matrix() {
if (isMainDiagonal)
for (std::size_t i = 0; i < R && i < C; ++i) m[i][i] = x;
else
for (std::size_t i = 0, j = C - 1; i < R && j >= 0; --j, ++i) m[i][j] = x;
}
template <std::size_t C2>
Matrix<T, R, C2, M> operator*(const Matrix<T, C, C2, M> &other) const {
Matrix<T, R, C2, M> res;
for (std::size_t i = 0; i < R; ++i)
for (std::size_t k = 0; k < C; ++k)
for (std::size_t j = 0; j < C2; ++j)
res.m[i][j] = (res.m[i][j] + m[i][k] * other.m[k][j] % M) % M;
return res;
}
Matrix<T, R, C, M> &operator*=(const Matrix<T, C, C, M> &other) {
return *this = *this * other;
}
void fill(T x) {
for (std::size_t i = 0; i < R; ++i)
for (std::size_t j = 0; j < C; ++j) m[i][j] = x;
}
T sum() const {
T res = 0;
for (std::size_t i = 0; i < R; ++i)
for (std::size_t j = 0; j < C; ++j) res = (res + m[i][j]) % M;
return res;
}
};a/(b*c) % p = a * b^-1 * c^-1
x&(-x)计算第一个非0位对应的权值(如2&(-2)=2,7&(-7)=1,6&(-6)=2)- 枚举子集
// n 最多取到14, 15
// 复杂度为O(3^n)
for (int i = 1; i < (1 << n); ++i) {
cout << bitset<32>(i) << ":\n";
for (int j = i; j; j=(j-1)&i) {
cout << "\t" << bitset<32>(j) << endl;
}
}x = a ^ (a << 13)/x = a ^ (a >> 13)，知道x求a的值，a, x都是64位无符号整数
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;
ull e(ull a1) {
ull a = a1 ^ (a1 << 7), b = a ^ ((a) >> 11), c = b ^ ((b) << 31);
return c ^ ((c) >> 13);
}
// most left part not changed: a ^ (a >> 13)
// most right part not changed: a ^ (a << 13)
ull f(ull x, int len, bool left) {
ull mask;
if (left) {
mask = ((1ull << len) - 1) << (64 - len);
for (int i = len; i < 64; i += len) {
ull m = mask >> i;
x = (x & (~m)) | (m & ((x >> len) ^ x));
}
} else {
mask = (1ull << len) - 1;
for (int i = len; i < 64; i += len) {
ull m = mask << i;
x = (x & (~m)) | (m & ((x << len) ^ x));
}
}
return x;
}
ull d(ull res) {
res = f(res, 13, true);
res = f(res, 31, false);
res = f(res, 11, true);
res = f(res, 7, false);
return res;
}
int main(int argc, char const *argv[]) {
ull x;
cin >> x;
cout << x << endl;
ull y = x ^ (x >> 13);
cout << y << endl;
cout << f(y, 13, true) << endl;
// cout << e(x) << endl;
// cout << d(e(x)) << endl;
return 0;
}- 曼哈顿距离 Manhattan Distance
在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。
例如在平面上，坐标(x1,y1)的i点与坐标(x2,y2)的j点的曼哈顿距离为: d(i,j)=|X1-X2|+|Y1-Y2|
- 欧式距离 Euclidean Distance
指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
如在二维空间，d(i,j)=sqrt((X1-X2)^2+(Y1-Y2)^2)
// for 1D:
// left1 < right2 && left2 < right1
// for 2D:
// overlap on both x and y根据三点坐标求面积
S=(1/2)*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)
- TODO
- 求x的平方根
z -= (z*z - x) / (2*z)直到不怎么改变 - 如何通俗易懂地讲解牛顿迭代法？
- 欧拉函数$\varphi(n);(n \in N^*)$：小于等于n的正整数中与n互质的数的个数（如$\varphi(3)=2$）
$\varphi(1)=1$ - 因为质数与小于它的每一个正整数都互质，所以如果n是质数，则$\varphi(n)=n-1$
- 如果$n=p^k;(p为质数,k\in N^*)$ ，则$\varphi(p^k)=p^k-p^{k-1}$
- 如果$n=p\times q$，而且p，q互质，有$\varphi(n)=\varphi(p\times q)=\varphi(p)\times \varphi(q)$
- 欧拉定理：对任意互素的a和n，有$a^{\varphi(n)}=1; (mod;n)$
- 费马小定理：$b^{p-1}=1(mod;p)$，故$b\times b^{p-2}=1(mod;p)$，所以b的逆元$x=b^{p-2}$
-
又称辗转相除法，是指用于计算两个正整数a，b的最大公约数 (GCD, Greatest Common Divisor)，扩展欧几里得除了求出最大公约数，还找出相应的x，y（其中一个很可能是负数）
- 有了最大公约数，求最小共倍数 (LCM, Least Common Multiple)就是:
a * b / gcd(a, b)
- 有了最大公约数，求最小共倍数 (LCM, Least Common Multiple)就是:
-
贝祖等式（贝祖定理）：是一个关于最大公约数的定理，对任何整数a，b和它们的最大公约数d，方程$ax+by=m$有整数解当且仅当m是d的倍数
- 特别的：方程$ax+by=1$有整数解当且仅当整数a和b互素
- 也就有了扩展欧几里得用来求逆元：a的逆元（模b下）是x%b （因为x可能为负数）
- ref: 扩展欧几里得算法详解
-
c++17中的numeric头文件中已经包含有gcd和lcm函数
-
# 欧几里得 def gcd (a, b): return a if b == 0 else gcd(b, a % b) # 扩展欧几里得 def egcd ( a , b ): if (b == 0): return 1, 0, a else: x , y , q = egcd( b , a % b ) # q = GCD(a, b) = GCD(b, a%b) x , y = y, ( x - (a // b) * y ) return x, y, q # 可以利用扩展欧几里得求逆元 def mod_inv(a,b): return egcd(a,b)[0]%b #求a模b得逆元int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int egcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int nx, ny; // b*nx + a%b*ny = q int q = egcd(b, a % b, nx, ny); // a*x + b*y // = a*ny + b*nx - b*(a/b)*ny // = b*nx + (a - b*(a/b))*ny // = b*nx + a%b*ny // = q x = ny; y = nx - (a / b) * ny; return q; } /** * @returns (x % b + b) % b where a*x + by = gcd(a, b) */ int mod_inv(int a, int b) { int x, y; egcd(a, b, x, y); return (x % b + b) % b; // possible that x < 0 } -
非递归扩展欧几里得算法？ref: 扩展欧几里得
拓展欧几里得，费马小定理(欧拉定理特例)，线性法
- TODO