[Coursera] Algorithms (princeton) (week1) 讨论帖

sanguine 发表于 2014-2-12 09:51
双UF也可以满足timing的……

不过同求单UF结题思路！

我一共用了1个UF，1个virtual TOP，1个boolean[N*N]跟踪是否open，1个int[N]跟踪最后一行各site的root。大家可以看看讨论区的帖子，有很多思路。

去掉virtual bottom以避免backwash是只用1个uf的情况下可以用的好思路~

双UF解决的，显示还是有bug，但所有test都通过了，这种情况怎么debug？

自己犯的几个错误
在percolates 里面用isFull检测
开始用的int 数组保存状态，memory通不过，用boolean之后可以了

prelude 发表于 2014-2-4 11:40
说一下在Eclipse 中
import 两个API jar包的问题，通过Project - properties - Libraries - add external ...

为什么我这么做后  import语句显示错误，可否给个截图。。。有成功的例子吗？而且文件解压发升错误。。。

sanguine 发表于 2014-2-12 16:56
看 https://class.coursera.org/algs4partI-004/forum/thread?thread_id=150

怎么那么长啊。。下次有时间再仔细看

rsun 发表于 2014-2-13 21:48
怎么那么长啊。。下次有时间再仔细看

所有的backwash的精华都在这了~

sanguine 发表于 2014-2-13 21:49
所有的backwash的精华都在这了~

印象中这门课的介绍里面好像说了要多去课堂的论坛。
唉，这么看来去看那个论坛的时间都比看书做作业的时间要长

rsun 发表于 2014-2-13 21:51
印象中这门课的介绍里面好像说了要多去课堂的论坛。
唉，这么看来去看那个论坛的时间都比看书做作业的时 ...

+1，我发现好多问题里面都有解答，而且非常耐心的--

而且你发的贴必有人回复~基本上速度很快~感觉超赞！！！

这个作业做得太爽了。。。各种小问题层出不穷，而到了100分以后还可以继续优化timing和memory cost。
先在加分贴交了作业，再继续优化，嘿嘿。不过最多只能提交10次，所以不能乱来~

需要注意：在percolationstats里不要把percolation作为instance variable，那样会造成惊人的内存占用，而应该在constructor里new一个，这样这部分内存会被回收掉。
我的体会：确实如上面所说，编号150的帖子里有基本上这个作业的所有精华。
               用2个uf、1个uf、0个uf都可以做出来。2个uf我没用，但可以想象到它的思路，以及因为多一个uf的instance variable，会有额外的memory cost。
               用递归track各个site的root变化，技术上来讲可以用，但当grid较大时，很容易stackoverflow。。。
               我用1个uf完成的，一般1个uf要配合1个virtual top/bottom。
               当然，不需要track最后一行所有site的root，可减少memory cost。
一个提示：在使用virtual top的情况下，需要思考在open()操作中，一旦周围有site是和最后一行connected的，union之后应该发生什么变化？
               用同样的思路，我觉得可以将virtual top也精简掉，也就进一步减少memory cost了。

请教各位，我得到的feedback都是这样的：

Percolation.java:2: error: package edu.princeton.cs.algs4 does not exist
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

PercolationStats.java:3: error: package edu.princeton.cs.introcs does not exist
import edu.princeton.cs.introcs.StdIn;

在自己的Eclipse里运行的好好的，是我哪里import的有问题吗？