LeetCode 分类刷题 —— Union Find
2019-08-23 本文已影响0人
一缕殇流化隐半边冰霜
Union Find 的 Tips:
- 灵活使用并查集的思想，熟练掌握并查集的模板，模板中有两种并查集的实现方式，一种是路径压缩 + 秩优化的版本，另外一种是计算每个集合中元素的个数 + 最大集合元素个数的版本，这两种版本都有各自使用的地方。能使用第一类并查集模板的题目有：第 128 题，第 130 题，第 547 题，第 684 题，第 721 题，第 765 题，第 778 题，第 839 题，第 924 题，第 928 题，第 947 题，第 952 题，第 959 题，第 990 题。能使用第二类并查集模板的题目有：第 803 题，第 952 题。第 803 题秩优化和统计集合个数这些地方会卡时间，如果不优化，会 TLE。
- 并查集是一种思想，有些题需要灵活使用这种思想，而不是死套模板，如第 399 题，这一题是 stringUnionFind，利用并查集思想实现的。这里每个节点是基于字符串和 map 的，而不是单纯的用 int 节点编号实现的。
- 有些题死套模板反而做不出来，比如第 685 题，这一题不能路径压缩和秩优化，因为题目中涉及到有向图，需要知道节点的前驱节点，如果路径压缩了，这一题就没法做了。这一题不需要路径压缩和秩优化。
- 灵活的抽象题目给的信息，将给定的信息合理的编号，使用并查集解题，并用 map 降低时间复杂度，如第 721 题，第 959 题。
- 关于地图，砖块，网格的题目，可以新建一个特殊节点，将四周边缘的砖块或者网格都 union() 到这个特殊节点上。第 130 题，第 803 题。
- 能用并查集的题目，一般也可以用 DFS 和 BFS 解答，只不过时间复杂度会高一点。
| Title | Solution | Difficulty | Time | Space | 收藏 |
|---|---|---|---|---|---|
| 128. Longest Consecutive Sequence | Go | Hard | O(n) | O(n) | ❤️ |
| 130. Surrounded Regions | Go | Medium | O(m*n) | O(m*n) | |
| 200. Number of Islands | Go | Medium | O(m*n) | O(m*n) | |
| 399. Evaluate Division | Go | Medium | O(n) | O(n) | |
| 547. Friend Circles | Go | Medium | O(n^2) | O(n) | |
| 684. Redundant Connection | Go | Medium | O(n) | O(n) | |
| 685. Redundant Connection II | Go | Hard | O(n) | O(n) | |
| 721. Accounts Merge | Go | Medium | O(n) | O(n) | ❤️ |
| 765. Couples Holding Hands | Go | Hard | O(n) | O(n) | ❤️ |
| 778. Swim in Rising Water | Go | Hard | O(n^2) | O(n) | ❤️ |
| 803. Bricks Falling When Hit | Go | Hard | O(n^2) | O(n) | ❤️ |
| 839. Similar String Groups | Go | Hard | O(n^2) | O(n) | |
| 924. Minimize Malware Spread | Go | Hard | O(m*n) | O(n) | |
| 928. Minimize Malware Spread II | Go | Hard | O(m*n) | O(n) | ❤️ |
| 947. Most Stones Removed with Same Row or Column | Go | Medium | O(n) | O(n) | |
| 952. Largest Component Size by Common Factor | Go | Hard | O(n) | O(n) | ❤️ |
| 959. Regions Cut By Slashes | Go | Medium | O(n^2) | O(n^2) | ❤️ |
| 990. Satisfiability of Equality Equations | Go | Medium | O(n) | O(n) |
