模板

副标题 / 摘要 并查集不是从 find 和 union 这两个函数名开始背。它要解决的问题是：怎样判断两个点是否已经属于同一个集合，并在看到一条连接关系时把两个集合合并。 预计阅读时长：10~12 分钟 标签：Hot100、并查集、Union-Find、DSU、图 SEO 关键词：并查集, Union-Find, DSU, find, union, count, 路径压缩 元描述：用 Python 从零推导并查集模板，讲清 parent、find、union、count、路径压缩和连通分量计数。 A — Algorithm（从集合合并压力开始） 小任务：不断合并集合，并回答连通性 假设有 5 个点： 0, 1, 2, 3, 4 一开始，每个点都是一个独立集合： {0}, {1}, {2}, {3}, {4} 现在依次发生两次合并： union(0, 1) union(1, 2) 我们想回答三个问题： 0 和 2 是否在同一个集合？ 3 和 4 是否在同一个集合？ 当前一共有几个集合？ 手工看答案是： {0, 1, 2}, {3}, {4} 所以： 0 和 2 在同一个集合 3 和 4 不在同一个集合 当前 count = 3 这就是并查集要解决的核心任务： ...

副标题 / 摘要 Trie 的重点不是背代码，而是理解“一个节点代表一个前缀”。只要这个模型稳定，插入、完整单词查询和前缀查询都会变成同一个循环。 预计阅读时长：8~10 分钟 标签：Hot100、Trie、前缀树、字典树 SEO 关键词：Trie, 前缀树, 字典树, children, is_end 元描述：用 Python 写一个最小 Trie 模板，讲清节点字段、children 走法、结束标记和循环 invariant。 A — Algorithm（从一个小任务开始） 小任务：同时回答完整单词和前缀 假设已经插入： app apple bat 现在要问： app 是不是完整单词？ ap 是不是某个单词的前缀？ apply 是否存在？ 这个小任务暴露了两个缺口： 只用哈希集合，可以快速判断完整单词，但不能自然回答前缀问题 只看路径存在，又会把 app 和 apple 的前缀关系混成一件事 Trie 要解决的就是：让很多字符串共享公共前缀，同时还能区分“前缀存在”和“完整单词存在”。 从压力反推要支持什么 我们先不管任何题目接口，只定义一个自己的模板： insert(word)：把一个单词插入 Trie search(word)：判断完整单词是否存在 starts_with(prefix)：判断是否存在以 prefix 开头的单词 最小结构图 插入 app 和 apple 后，结构可以想成： root └─ a └─ p └─ p [end] └─ l └─ e [end] 这里最重要的是： ...