刷题总结直播帖子

最近在帮忙朋友刷题，随手写了些总结和leetcode题号，干脆发上来大家看看。如果有人看的话我就一直写，也可以提出想要我写的部分，然后这个google doc是可以in line comment的，错误和建议请一并指出。我都是融合网上各种资料，都加了reference，如果侵权的话要告诉我哦。

我就不设置大米限制了。今天就先过一下union find，明天再贴别的，如果有人看的话会继续的。没人看这个帖子就会死掉。。。然后我这个写的会比较简单，大佬们直接跳过。

2019-11-27 Union Find


Algorithm 4th edition - 1.5 Case Study: Union-Find 有空可以看这个


总而言之就是
"人以类聚,物以群分"
(相似的在一起(合并)
查找自己属于哪一类(查找)
两个两个是否是同一类)
reference

总结一下它的各种操作就是

Union: 两个元素p和q,分别找到他们的根节点,然后将其中元素的root指向另外的一个元素的root
Find： 找到一个元素的根节点，找到parent的parent的parent一直到最终的parent
Connected: 判断两个元素p和q是不是最终指向同一个root
Count: 有多少不相关的root

我们来试试implement上面的这个

Code reference

我这个做法是用一个list来表示每个node，每个node的id就是自己的index，然后value就是root的index。还有一种做法是用dictionary或者自己定义一个新的node class

你可以用这个code测试一下

Code reference

我们上面的这个做法叫QuickFind，它并不是很efficient，因为我们每次union的时候需要遍历整个数据。还有另外一个做法叫QuickUnion

Code reference

这个方法不一样的是，在find这一步，一直找一直找到parent的parent直到root，然后union这一步就只需要通过find找到各自的root不需要遍历整个数组啦。是不是超级简单。同样的你可以用上面的code来测试一下。

但是你再看看，虽然我们改进的union这一步，但是find这一步其实比之前的叫QuickFind的find那一步慢了好多。。。 有没有看出他们为什么各自叫quickfind和quickuion？？

Quickfind就是find这一步很快，但是union慢
Quickunion就是union这一步很快，但是find慢

哎怎么办呢？其实还有一种做法叫，Weighted Quick Union来帮助QuickUnion加快find这个步。改进的方法可以是，在union之前，先判断两个树的大小（节点数量），将小点的树附加到大点的树上，这样，合并后的树的深度不会变得非常大。我们直接上图比较吧。

但是说实话它有没有好到哪里去，还有一种做法叫path compression。To implement path compression, we just add another loop to find() that sets the id[] entry corresponding to each node encountered along the way to link directly to the root. The net result is to flatten the trees almost completely, approximating the ideal achieved by the quick-find algorithm.

我们来做做看path compression怎么样。

Code reference
是不是超级简单？？


好了你把下面的题都做了吧。对了上面都是用数组做的，你也可以用dictionary哈或者自己定义一个TrieNode。

Leetcode作业
Longest Consecutive Sequence   
Friend Circles   
Couples Holding Hands
Redundant Connection
Number of Islands
Accounts Merge
Redundant Connection II
Surrounded Regions




补充内容 (2019-11-29 15:20):
上面path compression不小心写错了。 应该是 self.id[p] = self.find(self.id[p])

path compression 意义下的 find 函数写得不对哦。
你这个只是把每个点连到了它的父节点的父节点而已。

波风水门 发表于 2019-11-29 02:19
path compression 意义下的 find 函数写得不对哦。
你这个只是把每个点连到了它的父节点的父节点而已。

不好意思犯了这么低级的错误，感谢感谢我更正一下