Checkmate-patterns
图标
♔♕♖♗♘♙♚♛♜♝♞♟
车马杀王 - ♖ ♘ ⚔ ♚
马象杀王 - ♘ ♗ ⚔ ♚
车象杀王 - ♖ ♗ ⚔ ♚
车后杀王 - ♖ ♕ ⚔ ♚
象后杀王 - ♗ ♕ ⚔ ♚
单后杀王 - ♕ ⚔ ♚
车兵杀王 - ♖ ♙ ⚔ ♚
后兵杀王 - ♕ ♙ ⚔ ♚
闷杀 - ♘ ⚔ ♚
搜索与图论(一)
深度优先搜索(DFS)
回溯,剪枝。想清楚搜索顺序。回溯时注意恢复现场。
搜索框架
排列数字
123456789101112131415161718192021222324252627282930313233#include <iostream>using namespace std;const int N = 10;// 记录是否使用过bool st[N];int n;// 保存每次搜索的路径。path 用于存每个方案。int path[N];// u 代表搜索第几层,第 0 层时,填写了 0 个元素void dfs(int u) { if(u == n) { for(int i=0;i<n;i++) cout << path[i] << " "; cout << endl; return; } // 在每一层时,从 1 到 n 依次查看当前位置能不能填 i for(int i=1;i<=n;i++) ...
C++ STL 容器
vector
变长数组。倍增思想。
系统为某一程序分配空间时,所需时间与分配的空间大小无关,与申请次数有关。
初始时,为 vector 申请 32 个空间长度,当空间占满后,申请 2 倍大小的空间,然后将原来的 32 个空间中的内容复制到新的空间中,继续使用新的空间。
复制元素均摊后时间复杂度为 O(1)O(1)O(1)。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <vector>#include <iostream>using namespace std;int main () { // 最简单用法,初始化一个 vector vector<int> a; // 初始化一个长度为 10 的 vector vector<int> b(10); // 初始化一个长度为 10 的 vector,并将其中的元素都设置成 3 vector< ...
哈希表
哈希表
适合将定义域很大的数据映射到值域较小的集合。是一般意义上的哈希,离散化是一种特殊的哈希,需要保序,哈希函数需要单调递增。
x∈(10−9,109),h(x)∈(0,105)x\in(10^{-9}, 10^{9}), h(x)\in(0, 10^{5})x∈(10−9,109),h(x)∈(0,105)
哈希函数一般为:h(x)=x \mod 质数
质数应尽可能离 2n2^{n}2n 要远,这样冲突的概率最小。
存储结构
开放寻址法
只使用一个一维数组,经验值开辟 2~3 倍元素个数的数组空间。
拉链法
开一个一维数组,长度为值域大小。每次算出一个哈希值 h[x] = y,就在 y 的位置上开一个链表,在链表末尾记录 x 的值。
查询某个数 x 是否在哈希表中,首先计算出哈希值 h[x] = y,然后遍历哈希值对应的数组位置 y 上的链表,查看链表中是否存在 x。
总结:一个数组,拉了很多链表。数组插槽编号对应的是哈希值,数组插槽内容对应的是链表节点编号。链表节点中存的是原始数据值。
字符串哈希方式
将字符串看成一个 p 进制数。
例如:“ABCD”
hash((AB ...
堆
堆的操作:
插入一个数
求集合中的最小值
删除最小值
*删除任何一个元素
*修改任何一个元素
堆的存储
堆是一个完全二叉树。
存储:使用一个一维数组存储,下标从 1 开始存。完全二叉树一般都用一维数组存储。
小根堆:每个点都小于等于左右儿子。
xxx 的左儿子:2x2x2x
xxx 的右儿子:2x+12x + 12x+1
基础操作
down(x)
down(x): 把一个节点往下移动。需要与左右两个孩子比较,与小的孩子交换。时间复杂度与树的高度成正比,因此是 O(log(n))O(log(n))O(log(n))
up(x)
up(x): 把一个节点往上移动。只需与父节点比较,如果比父节点小,就与父节点交换。时间复杂度与树的高度成正比,因此是 O(log(n))O(log(n))O(log(n))
再来看堆的操作
插入一个数
1heap[++size] = x; up(size);
求集合中的最小值
1heap[1]
删除最小值
用堆的最后一个元素覆盖堆顶的元素。将最后一个元素删除。将堆顶元素下移。
1heap[1] = heap[size--]; down(1); ...
postgres数据恢复备份
1$ psql -U {数据库用户名} -h {数据库host} -p {端口} -d {数据库} -f db-back.dump
并查集
并查集能快速处理以下操作:
将两个集合合并
询问两个元素是否在一个集合中
时间复杂度近乎 O(1)
基本原理
每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点,p[x] 表示 x 的父节点。
如何判断树根?
if(p[x] == x)
如何求集合编号?
while(p[x]!=x) x=p[x];
如何合并两个集合?
p[x] = y
优化
每次找到根节点后,进行路径压缩。
模板题
原题链接
12345678910111213141516171819202122232425262728293031323334#include <iostream>using namespace std;const int N = 100010;int p[N];int n,m;// 返回 x 所在集合的编号(祖宗节点) + 路径压缩。int find(int x) { // 只要 x 的父节点不是祖宗节点,就让 x 的父节点指向 x 的祖宗节点 if(p[x]!=x) p[x] = find(p[x]); return ...
分阶段构建docker镜像
官方文档文档
当构建 docker 镜像时,每运行一次 RUN 指令就会为镜像增加一个层,因此为了减小镜像体积经常看到如下样式的构建命令,将多个命令合成一行多次使用了 && 符号。:
12RUN go get -d -v golang.org/x/net/html \ && CGO_ENABLED=0 GOOS=linux go build -a -installsuffix cgo -o app .
分阶段构建镜像的思路在于:可以将先使用一个大而全的镜像构建程序,然后将构建产物复制到一个精简版本的镜像。
1234567891011FROM golang:1.7.3 AS builderWORKDIR /go/src/github.com/alexellis/href-counter/RUN go get -d -v golang.org/x/net/htmlCOPY app.go .RUN CGO_ENABLED=0 GOOS=linux go build -a -installsuffix cgo -o app .FROM alpine:la ...
KMP 算法
高速在一个字符串中查找子串。时间复杂度只需要 O(n)。n 是字符串的长度。
next[i] = j 的含义:在模式串 p 中,以 i 结尾的,满足最长前缀和后缀关系,前缀的最后一个位置为 j。即 P[1 ~ j] = P[i - j + 1, i] 相等。
s 串和 p 串都从下标 1 开始存。
模式串中的指针不用每次匹配失败时都退到 0。
12345678910111213141516171819202122232425262728293031#include <iostream>using namespace std;const int N = 1e5 + 10;const int M = 1e6 + 10;int n,m;char p[N], s[M];int ne[N];int main() { cin >> n >> p+1 >> m >> s+1; // 求 next 数组的过程,模式串自己跟自己比较,过程中记录 next 数组 for(int i=2,j=0;i<=n;i++) ...
单调队列
单调队列的应用:求滑动窗口中的最大值。
原题链接
123456789101112131415161718192021222324252627282930313233343536#include <iostream>using namespace std;const int N = 1e6+10;int n,k;int q[N], a[N];int tt, hh;int main() { scanf("%d%d", &n, &k); for(int i=0;i<n;i++) { scanf("%d", &a[i]); } hh=0, tt=-1; for(int i=0;i<n;i++) { // 队头元素已经不在滑动窗口中了,就删掉 if(hh <= tt && q[hh] < i-k+1) hh++; // 如果当前元素比队尾元素小,就把队尾元素 ...