每日leetcode第0045天 0765. Couples Holding Hands

今天是七夕节,樊老师来做leetcode第765题《情侣牵手》。

这一道题是问最少需要交换几次,所以我们当然可以使用广度优先搜索来解决。

但看了很多人的分析后,我理清了思绪,这道题目最适合的解法应该是并查集。

并查集:union-find 是一种查找是否在一个帮派的数据结构。

这道题目的本质有点类似于魔方盲拧,我们需要连通每个块,但也会存在多个小循环。

若我们发现了小循环便是多了一个分量(component)。

回到这道题目。

每一个分量中,需要交换的次数为 分量当中情侣对数 减去 1。

总共需要的交换次数就是 所有分量的情侣对数 减去 所有分量里面的1,

也就是 情侣总对数n 减去 分量的数量 。

 

分量怎么计算呢?可以先定为n,也就是情侣对数。

每一次连接两个量的时候,我们的分量数减少。

若这两个人不需要连接,就不需要减少。

 

我们尝试连接两个相邻座位的时候还使用了一个技巧。

让0和1都变成0,让2和3都变成1,让4和5都变成了2。

那就是直接除以2。

这样就可以很快来判断两位是不是情侣了。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。