2.16 ✅ Union Find

Union Find #

  • 灵活使用并查集的思想,熟练掌握并查集的 模板,模板中有两种并查集的实现方式,一种是路径压缩 + 秩优化的版本,另外一种是计算每个集合中元素的个数 + 最大集合元素个数的版本,这两种版本都有各自使用的地方。能使用第一类并查集模板的题目有:第 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 解答,只不过时间复杂度会高一点。
No.TitleSolutionDifficultyTimeComplexitySpaceComplexityFavoriteAcceptance
0128Longest Consecutive SequenceGoMediumO(n)O(n)❤️48.5%
0130Surrounded RegionsGoMediumO(m*n)O(m*n)36.7%
0200Number of IslandsGoMediumO(m*n)O(m*n)57.0%
0399Evaluate DivisionGoMediumO(n)O(n)59.6%
0547Number of ProvincesGoMediumO(n^2)O(n)63.7%
0684Redundant ConnectionGoMediumO(n)O(n)62.2%
0685Redundant Connection IIGoHardO(n)O(n)34.1%
0695Max Area of IslandGoMedium71.8%
0721Accounts MergeGoMediumO(n)O(n)❤️56.3%
0765Couples Holding HandsGoHardO(n)O(n)❤️56.6%
0778Swim in Rising WaterGoHardO(n^2)O(n)❤️59.8%
0785Is Graph Bipartite?GoMedium53.1%
0803Bricks Falling When HitGoHardO(n^2)O(n)❤️34.4%
0839Similar String GroupsGoHardO(n^2)O(n)48.0%
0924Minimize Malware SpreadGoHardO(m*n)O(n)42.1%
0928Minimize Malware Spread IIGoHardO(m*n)O(n)❤️42.7%
0947Most Stones Removed with Same Row or ColumnGoMediumO(n)O(n)58.9%
0952Largest Component Size by Common FactorGoHardO(n)O(n)❤️40.0%
0959Regions Cut By SlashesGoMediumO(n^2)O(n^2)❤️69.1%
0990Satisfiability of Equality EquationsGoMediumO(n)O(n)50.5%
1020Number of EnclavesGoMedium65.5%
1202Smallest String With SwapsGoMedium57.7%
1254Number of Closed IslandsGoMedium64.1%
1319Number of Operations to Make Network ConnectedGoMedium62.1%
1579Remove Max Number of Edges to Keep Graph Fully TraversableGoHard53.2%
1631Path With Minimum EffortGoMedium55.7%
——————————————————————-——-—————-—————————-————-————-

⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者