字典树，即Trie树，又称单词查找树或键树，是一种树形结构。 典型应用是用于统计和排序大量的字符串（但不仅限于字符串）， 所以经常被搜索引擎系统用于文本词频统计。
它的优点是：最大限度地减少无畏的字符串比较，查询效率比哈希表高。
- 结点本身不存完整单词；
- 从根节点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；
- 每个节点的所有子结点路径代表的字符都不相同。
Trie树的核心思想是空间换时间 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
并查集的Java实现：
class UnionFind {
private int count = 0;
private int[] parent;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
}指定位置的位运算
- 将x最右边的n位清零：x&(~0<<n)
- 获取x的第n位值(0或者1):(x>>n)&1
- 获取x的第n位的幂值：x&(1<<n)
- 仅将第n位置为1：x|(1<<n)
- 仅将第n位置为0：x&(~(1<<n))
- 将x最高位至第n位（含）清零：x&((1<<n)-1)
实战位运算要点
- 判断奇偶： x%2 == 1 --> (x&1) == 1 x%2 == 0 --> (x&1) == 0
- x>>1 --> x/2 即：x = x /2; --> x = x >>1; mid = (left + right) / 2; --> mid = (left + right) >> 1;
- X = X & (X - 1) 清零最低位的1
- X&-X => 得到最低位的1
- X&-X => 0