字典树

• 字典树（$Trie$ 树）是一种由 “节点” 和 “带有字符的边” 构成的树形结构。
• 典型应用是用于统计和排序大量的字符串（但不仅限于字符串），经常被搜索引擎系统用于文本词频统计。
• 优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
• 基本性质
  • 节点本身不保存完整单词。
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的单词。
  • 每个节点出发的所有边代表的字符都不相同。
  • 节点用于存储单词的额外信息（例如频次）。
    
• 内部实现
  
  • 字符集数组法
    • 每个节点保存一个长度固定为字符集大小（例如 $26$）的数组，以字符为下标，保存指向的节点。
    • 空间复杂度：$O(节点数\ast 字符集大小)$。
    • 查询的时间复杂度： $O(单词长度)$。
    • 适用于较小字符集，或者单词短、分布稠密的字典。
  • 字符集映射法
    • 把每个节点上的字符集数组改为一个映射（词频统计：$hashmap$，排序：$orderedmap$）。
    • 空间复杂度：$O(文本字符总数)$
    • 查询的时间复杂度：$O(单词长度)$。
    • 适用性更广。
• 核心思想
  • 空间换时间，无论是保存树的结构、字符集数组还是字符集映射，都需要额外的空间。
  • 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
  • 分组思想：前缀相同的字符串在同一子树中。

---

LeetCode 练习题

• 208. 实现 Trie (前缀树)
• 212. 单词搜索 II

---

并查集

• 基本用途：处理不相交集合的合并和查询问题 → 处理分组问题 → 维护无序二元关系。
• 基本操作：
  • $MakeSet(s)$：建立一个新的并查集，其中包含 $s$ 个集合，每个集合里只有一个元素。
  • $UnionSet(x,y)$：把元素 $x$ 和元素 $y$ 所在集合合并。要求 $x$ 和 $y$ 所在的集合不相交，如果相交则无需合并。
  • $Find(x)$：找到元素 $x$ 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
• 内部实现

  • 每个集合是一个树形结构。

  • 每个节点只需要保存一个值：它的父节点。

  • 最简单的实现是只用一个 $int$ 数组 $fa$，$fa[x]$ 表示编号为 $x$ 的节点的父节点，根节点的 $fa$ 等于它自己。

  • 初始化 $MakeSet$
    

  • 合并 $UnionSet$
    

  • 查询 $Find$ + 路径压缩

    • 在 $Find(x)$ 的同时把 $x$ 和 $x$ 的所有祖先直接连到根节点上，下一次就可以一步走到根了。
      

    class DisjointSet {
    public:
    	DisjoinSet(int n) {
    		fa = vector<int>(n, 0);
    		for (int i = 0;i < n;i++) fa[i] = i;
    	}
    	int find(int x) {
    		if (x == fa[x]) return x;
    		return fa[x] = find(fa[x]); // 压缩路径
    	}
    	void unionSet(int x, int y) {
    		x = find(x), y = find(y);
    		if (x != y) fa[x] = y;
    	}
    private:
    	vector<int> fa;
    }
    

---

LeetCode 练习题

• 547. 省份数量

---