端点星

图标 ♔♕♖♗♘♙♚♛♜♝♞♟ 车马杀王 - ♖ ♘ ⚔ ♚ 马象杀王 - ♘ ♗ ⚔ ♚ 车象杀王 - ♖ ♗ ⚔ ♚ 车后杀王 - ♖ ♕ ⚔ ♚ 象后杀王 - ♗ ♕ ⚔ ♚ 单后杀王 - ♕ ⚔ ♚ 车兵杀王 - ♖ ♙ ⚔ ♚ 后兵杀王 - ♕ ♙ ⚔ ♚ 闷杀 - ♘ ⚔ ♚

深度优先搜索（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++)
...

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); ...

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 镜像时，每运行一次 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 ...

高速在一个字符串中查找子串。时间复杂度只需要 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++; // 如果当前元素比队尾元素小，就把队尾元素 ...