一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 806|回复: 12
收起左侧

Algorithm Princeton part II (week5)

[复制链接] |试试Instant~ |关注本帖
18258170717 发表于 2015-4-23 17:11:13 | 显示全部楼层 |阅读模式

[Coursera]Algorithm, part II #5 - 2015-3-20@Princeton

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Week5真心是拖了好久好久,上课的内容也是很难。。大家多多努力吧。先上图

Week5

Week5

说说我的思路吧,根据hint上的提示,先搞清楚BoggleBoard,其实就是大致了解它长啥样。
我在构造dict的时候走了点弯路,一开始用了TrieST,然后String key的最后一个character存放分值,当时以为这样找到string后直接搞出值很牛,后来发现在getAllValidWords返回String就行了,而scoreOf再去找分值。这里应该先看完所有的API然后再决定dictionary的类型。
最后我确定用TrieSET,这个可以在最后一个character存放isString,来判断时候为String。getAllValidWords方法中,先将board变成Graph,和之前学过做过的比较相似,把各个vertices之间的edge加上。
接着就到了关键的部分,我们是要用dfs找到合适的string,长度大于2,并且存在dictionary中。这里如果发现下一个char在dictionary trie的next[]里没有,那就不用继续找下去了。这里我是在trie改了R,以及加上了一些field与method,可以增减char,并得到String。(一开始我也打算在BoggleSolver里面写,但发现Node中的next是private的不能拿到外面来,所以还不如重新写一下trie,用新的API去写Solver,这样看起来更加清晰)。
关于Q的问题,如果dfs中下一个char是Q,那么就要检查下下个是不是U,是U就加进去,不是U则返回(不可能继续了),在退出的时候也要注意减去两个char,正常的是减去一个char。(可能这么说不太明白,但写的时候注意吧,之前没检查出来)

评分

1

查看全部评分

Rmysterio 发表于 2015-4-24 14:44:30 | 显示全部楼层
我是重写了TST
回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-5-4 15:16:03 | 显示全部楼层
Screen Shot 2015-05-04 at 15.13.48.png
中间出去玩了几天,回来后断断续续写了2天,感觉自己还是太渣,一碰头到递归问题,就容易乱

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

热情bruce的 发表于 2015-5-10 07:02:55 | 显示全部楼层
谢谢你们!谢谢coursera!
Screen Shot 2015-05-09 at 7.02.32 PM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

thomaschan 发表于 2015-5-15 18:56:25 | 显示全部楼层
这次作业上手倒是不难,但是优化过程实在是太揪心了,拿满分真心不容易
2015-05-15 18:21:38 的屏幕截图.png
2015-05-15 18:22:29 的屏幕截图.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-5-21 16:44:32 | 显示全部楼层
最后两个timing实在是搞不定了。心塞。
想知道isPrefix和dfs从recursive变成non-recursive真的有差么?我自己算了时间还是通不过。
虽然我知道的确重复计算了很多subroutine. 但是,每次都附带了挺多状态,感觉用recursive还挺好的,每一个subroutine维护一个visited的集合。代码看着还算干净。

Trie用的是tenacy search trie,自己稍微改写一下下了。感觉这个算法的关键就是基于当前的trie node和char是否存在subtrie (是否是valid prefix) ,如果不存在直接忽略这条路。感觉还是挺有意思的。第一次接触Trie,真的很震撼。
a5.PNG

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-5-21 16:47:15 | 显示全部楼层
我认为你并不需要在dfs的时候判断prefix是Qu还是Q, 不管是什么,都可以判断是不是valid prefix

也可能是理解错了你的意思
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-5-21 16:48:03 | 显示全部楼层
gjxwin 发表于 2015-5-4 15:16
中间出去玩了几天,回来后断断续续写了2天,感觉自己还是太渣,一碰头到递归问题,就容易乱

请问你recursive的方法timing还可以通过?好神奇
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-5-21 16:53:57 | 显示全部楼层
我认为你并不需要在dfs的时候判断prefix是Qu还是Q, 不管是什么,都可以判断是不是valid prefix

也可能是理解错了你的意思
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-5-24 22:32:24 | 显示全部楼层
好久没上这门算法课了,5.30就要截止了。想想还是得硬着头皮把最后这两个作业给做完。视频下了以后还可以看。
这次作业不难,但是挺繁琐,就和上次那个baseball illumination一样,你得在写代码之前就想好用什么数据结构来解决什么问题。
我一开始用的是自己写的递归。同样,为了避免DFS到已经扫描过的点,我愚蠢的把已经遍历的点放进了链表,进入的时候先遍历链表,看看是否已经有了该节点。退出的时候把尾结点删除就好了。
然后词典用什么数据结构存储。因为我发现结点不需要存储什么value,所以就直接用了 TrieSET,相应字符串尾结点就为true即可。然后存储词典的时候,我最后决定不需要考虑QU的问题。如果碰到了Q,最节约的方法是,往后跳两格,因为这个作业就是默认Q后面一定跟着U。但其实把U插入在Q后面,也不会占用多少资源。然后就成功把词典存储在了TrieSET中。
接着,我之前的思路就是自己写递归,然后后来发现链表太影响资源了,就打算自己重写一个布尔数组。不停地重置。后来想想,还是先上这里看下大神们什么思路再说吧。。。
于是看到了说用图。因为作业的提示里面说没必要用图。我一开始也没想到用图。后来想到了用图,又有一个问题。DFS里面,每个节点一定只能被遍历一次。但在这道题目的情景里面不是。于是我发现我思维定式了。我总是觉得只能一成不变得使用网上提供的类,后来发现可以改。那么就把重置布尔数组的操作全部加了进去。然后整个作业就差不多了。
这次作业代码量不多。首先拿TrieSET存储字典。并且把R改成26. 之后的 char[c]  其中一部分改成 char[c - 65]。然后根据board生成图。然后生成DFS类来处理这个图。改写其中的dfs方法。最关键的就是重置布尔数组。还有就是按照他的规则来进行相应的处理。然后将符合条件的字符串加入HashSet中。返回回去。 score方法就比较简单了。
还有个注意的地方。我一开始写好程序的时候发现特别慢。后来上来看了大家的评论,发现的确还是有一个无意义的工作。就是根据prefix确定之后是否有以此prefix开头的字符串。我当时偷懒了,直接调用了他的方法。然后如果返回的是null,那就代表没有。但其实只需要看next char对应在next[]中是否为空。如果是空的,就代表没有以此开头的字符串。
差不多就这样了。
PS:毕业季事情真他妈多啊。
assignment9_Score.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-5-24 22:33:36 | 显示全部楼层
czbnlzd920706 发表于 2015-5-24 22:32
好久没上这门算法课了,5.30就要截止了。想想还是得硬着头皮把最后这两个作业给做完。视频下了以后还可以看 ...

哦,对了。没能拿满分是因为最后一个测试过不了。
test scoreOf() on various dictionaries
  *  dictionary = dictionary-algs4.txt
      -  failed on trial 1 of 1000
      -  word = BARBER
      -  student   score = 3
      -  reference score = 0
  *  dictionary = dictionary-common.txt
      -  failed on trial 1 of 5000
      -  word = SUBPROBLEM
      -  student   score = 11
      -  reference score = 0
  *  dictionary = dictionary-shakespeare.txt
      -  failed on trial 3 of 10000
      -  word = BELOVE
      -  student   score = 3
      -  reference score = 0
  *  dictionary = dictionary-nursery.txt
  *  dictionary = dictionary-yawl.txt
      -  failed on trial 16 of 20000
      -  word = TIMANDRA
      -  student   score = 11
      -  reference score = 0
==> FAILED

不知道什么情况,想想算了。
回复 支持 反对

使用道具 举报

L.r_yoga 发表于 2016-6-2 10:50:11 | 显示全部楼层
太懒就把jar包里的TST刨出来加了一个hasPrefix()用来存dictionary了~recursive找word, 发现最后两个timing过不去的时候,试过把TrieST刨出来,发现memory挂了= =。修炼不够留坑再补╰( ̄▽ ̄)╭
PS。TrieST中Node的value不是generic,强制cast有warning,但实际上constructor里都限制了val的类型,求问大神们除了改成generic,有没有更方便的办法可以解决这个问题~
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

L.r_yoga 发表于 2016-6-2 10:50:47 | 显示全部楼层
czbnlzd920706 发表于 2015-5-24 22:33
哦,对了。没能拿满分是因为最后一个测试过不了。
test scoreOf() on various dictionaries
  *  dicti ...

是不是没有查word有没有在dic里
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 09:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表