并查集
并查集能快速处理以下操作：
将两个集合合并
询问两个元素是否在一个集合中
时间复杂度近乎 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。
1234567891011121314151617181920212223242526272829303132#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 &l ...
单调队列
单调队列的应用：求滑动窗口中的最大值。
原题链接
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++; // 如果当前元素比队尾元素小，就把队尾元素 ...
C++ 加速输入输出
用以下代码可以加速 cin、cout 的输入输出速度。但还是比 scanf、printf 慢一点。
12cin.tie(0);ios::sync_with_stdio(false);
禁止搜索引擎爬取网站
将以下代码插入到 server 域中
123456if ($http_user_agent ~*"qihoobot|Baiduspider|Googlebot|Googlebot-Mobile|Googlebot-Image|Mediapartners-Google|Adsbot-Google|Feedfetcher-Google|Yahoo!Slurp|Yahoo! Slurp China|YoudaoBot|Sosospider|Sogou spider|Sogou webspider|MSNBot|ia_archiver|Tomato Bot") { return 403;}
配置容器应用的几种方式
启动容器时直接通过命令传递参数。
缺点：只能传递有限的配置，无法为应用生成复杂的配置，某些配置不支持通过命令行参数进行传递。
将定义好的配置文件硬编码进镜像文件。
缺点：每次修改配置文件需要重新构建镜像。
通过环境变量传递配置数据。
缺点：无法在容器应用运行过程中更新环境变量。
通过 Docker 卷传送配置文件。
缺点：分布式环境下，镜像运行在不同的机器，需要给每台机器本地都放置配置文件。
分布式环境中的配置管理系统，将配置内容从代码中完全分离出来，进行集中管理。K8S 中的 ConfigMap 就是做配置文件集中管理的。
k8s secret 资源
创建 docker-registry 类型的 secret
1$ kubectl create secret docker-registry regsecret --docker-server=registry.cn-beijing.aliyuncs.com --docker-username={用户名} --docker-password={密码} -n {命名空间}
创建 tls 证书类型的 secret
1$ kubectl create secret tls {密钥名称} --key={私钥路径} --cert={证书路径} -n {命名空间}
创建 generic 类型的 secret
1$ kubectl create secret generic {密钥名称} --from-literal={键名}={值} --from-literal={键名 ...
双链表
原题链接
双链表需要 e[i] l[i] r[i] idx 来存储。
e[i] 表示标号为 i 的节点的值。
l[i] 表示标号为 i 的节点左边的节点标号。
r[i] 表示标号为 i 的节点右边的节点标号。
idx 表示当前分配到的节点标号。new Node() 等价于 e[idx]。
标号为 0、1 两个节点为双链表的起始和终止节点，不存储实际数据。初始化时 r[0] = 1, l[1] = 0, idx = 2。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include <iostream>#include <string.h>using namespace std;const int N = 1e5 + 10;int l[N], r[N], e[N], idx;int m;void init() { // 编号为 0 的节点是双链表最左 ...
C++ 数组下标可以为负数
在 C++ 中数组的下标可以为负数：
123456789101112131415161718#include <iostream>using namespace std;int main() { int intArray[1024]; for (int i = 0, j = 0; i < 1024; i++) { intArray[i] = j++; } cout << intArray[512] << endl; // 512 int *midArray = &intArray[512]; // 指向了数组中间的数据 cout << midArray[-256] << endl; // 256 cout << intArray[-256] << endl; // 得到不可预知的结果}
