AlgorithmUnion Find

LeetCode 分类刷题 —— Union Find

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)
支付宝扫码打赏 微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章

一缕殇流化隐半边冰霜's Picture
一缕殇流化隐半边冰霜

我是于德志 (@halfrost),一名来自中国的 iOS 开发者,已退役 acmer 。现居上海。从 2016 年开始写博客记录自己技术成长的一点一滴,到年底,成为简书推荐作者,2016 年度掘金最优秀的 10 佳原创作者。吾笃信:天道酬勤,勤能补拙。地道酬实,实能不弱。人道酬德,德能补寡。 目前就职于 饿了么 。

Shanghai「上海」 https://halfrost.com

Subscribe to Halfrost's Field | 冰霜之地

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!

Comments