[Coursera] Algorithms, Part Ⅰ (Week 1)

qijiaxing 发表于 2013-9-1 13:31
关于BACKWASH，哪位同学能给点提示么？
我现在的做法是：
一个数组记录是否open

我觉得必须使用两个个WQUF。
第一个WQUF连接顶部和底部的两个virtual cell，用于应答 percolates()；
第二个WQUF仅仅连接顶部的virtual cell，用于应答 isFull()。

至于为什么一定要两个，我的理解是，union-find结构用来揭示哪些节点是联通的，但是percolation问题包含了两个问题，一是整个结构是否上下连通，二是：某一节点是不是“自上而下”连通。所以仅用一个union-find是不够的。

作业1终于交了。timing的第一部分总是不能过，是不是必须要用WQUF来实现呀？我的没用，但是结果都对的。

leoz0610 发表于 2013-9-1 16:09
作业1终于交了。timing的第一部分总是不能过，是不是必须要用WQUF来实现呀？我的没用，但是结果都对的。

对的，应该是这个问题，要求用WQUF的。

是不是不翻墙看不了coursea?

zhangshv123 发表于 2013-9-2 10:08
是不是不翻墙看不了coursea?

可以看的

才搞完 求学分。

同学中，刚跟完了第一章

Week 1:

Week 1:
上周就搞定了，求学分~~

我也是failed 在backwash上....如果我只用顶点记录，不用底点记录的话，那么查找full就要寻混整个最底下一排，时间上又跟不上...