JavaScript 刷 LeetCode 拿 offer- 并查集
前言
并查集是合并集合的方式,对于一些关联性的集合,合并查询的方式可以使得题目分类处理,是一种题型的解决方案,这里最关键是构思好集合之间的关联关系;
在这一 part 中,仅仅只是对部分题做了了解学习,远远没有达到可以手撕的程度,但是面试过程中遇到的并不算特别多,所以属于一个了解补充的 part,大家可以学习学习,还是挺有意思的;
下一 part 做分治法
正文
这是一篇水文,国庆回家也就坚持每天做一丢丢题目,然后保持一下手感,而并查集确实比较好的锻炼一下脑子,脑子不够转不过来,所以可以尝试学习并做一下,他的基本模板不会很复杂,基本如下:
当然,具体问题上,可能可以简化或者强化 connect 方法,来解决具体的问题,这就需要同学自己去学习探讨了;
最后将几道例题奉上,节日结束,继续搬砖吧;
参考视频:传送门
题目
547. 省份数量
分析
每一个城市都有可能是一个省份,而只有是连接的城市,就合并为一个省份,最后剩下的集合就是省份
所以可以直接用 parents 数组缓存,其中 index 表示自己的唯一表示,value 表示指向集合城市
当我们遇到 isConnected[i][j] === 1 的时候,将两个城市连接起来,最后得到的值就是连接状况
最后的 parents[index] === index 的数量,就是集合的数量
时间复杂度 O(n), 空间复杂度 O(n)
721. 账户合并
分析
首先题目已知邮箱属于唯一的一个 name,而 name 的名字是可以相同但是代表不同的人的,所以 name 只能算是一个标记而已,所以一开始做合并操作不需要计算 name,用 email_name_map 缓存起来,直到最后再用
由于邮箱是一个字符串,而这里显然需要将同一个用户的邮箱缓存到一起,所以这里用下标来标记不同的邮箱,并缓存到 email_index_map
开始使用并查集,将同一个用户下 email 连接起来
连接完之后,现在在并查集 parents 里面都是一些 index 表示的东西,他们代表一种关联逻辑,
但是具体怎么重新排列,需要通过 email_index_map 来找到找到原始的 email,然后查找是否属于同一个集合的,然后再缓存在在一起;
这个时候所有相同集合的值后缓存在了 email_index_map 的 value 中了,取出来,排序,然后从 email_name_map 取出 name,然后合并成一个数组,然后作为二维数组的一个 item push 到 merge 数组里
时间复杂度 nlogn -- 每一次并查集合并的时候,需要进行 2 次查找 1 次合并;空间复杂度 O(n)
924. 尽量减少恶意软件的传播
分析
创建并查集,并将可以连接在一起的构成一个集合
通过并查集,查找到每个并查集的 root 节点,并用 injectedMap 缓存根节点和对应的缺陷节点数
初始化最大子节点数量 maxSize 和返回值 ret
再次遍历 initial 错误节点,然后找到每个节点对应的根节点出现的次数 count,如果超出 1, 那么干掉当前节点 node,依然会有新的节点最后会感染 root 节点,也就是当前集合还是会有感染源;所以没啥意思
如果都是只有一个感染源的集合,那么就判断这个集合的大小,集合越大,则删除当前污染源节点效果更好;如果集合一样大,就删除小的那一个;
时间复杂度 O(n),空间复杂度 O(n)
1319. 连通网络的操作次数
分析
对于 n 台电脑,至少需要 n-1 条线才能把他们完全连接前来
对于 n 台机器,如果进行并查集连接后,查看集合的数量,我们最后希望只剩下一个 1 个集合,多出来的集合就是抽取网线进行操作的操作数量
并查集关键降低复杂度的操作 _find, 如果用的是迭代,那么就只需要遍历一遍,否则用递归就还要回来
最终的结果可以在 _connect 连接过程中找出最终集合的大小,也可以根据最后的 parents 的下标和值相等的值来获取
时间复杂度 O(n)
1202. 交换字符串中的元素
分析 -- 超时了
不断的交换 pairs ,使得最终的字符串 str 是最小的字符串,所以就是要将 pairs 中同一集合的找出来,按顺序排好,然后再组合好
因为同一集合之间可以联通,所以可以经过多次之后,将集合中最小的字符串放在其它字符之前
用一个 root_strArr 来缓存根节点下的字符串数组,然后每次合并的时候,根据 root_strArr 来拍平字符串的缓存,然后缓存两者的数组,最后得到根节点下缓存的集合数组
最后在交换字符串的时候,每一次都找到这个集合剩余的最小的那个值,然后输出出去
超时了
然后以为做了一些细微的优化,比方说字符串比较比较耗时,转成 Unicode 编码; 使自定义的有序数组合并等,但是都超时了
然后分析时间复杂度,如果在连接过程中就进行排序操作,那么复杂度就是 O(n2) n 是 s.length, 而已知 s.length < 10^5, 所以 n2 超出了 10^8, 所以基本不可以通过了;
分析
amazing,上面一直超时,一直想在连接的时候进行排序操作,所以自己进行有序数组的排序,比较转成 unicode 格式的,都超时了
反而在集合合并的时候直接合并数组,然后在一次性将每个集合进行排序,最后得到的结果可以 ac
遍历集合数量,然后进行集合排序,相当于是对所有字符的排序,时间复杂度是 nlogn 其中 n 是 s.length;
评论