推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1581|回复: 19
收起左侧

Berkeley CS 61B Data Structures(in Java) lab13

[复制链接] |试试Instant~ |关注本帖
pirateshadow 发表于 2016-5-5 17:05:38 | 显示全部楼层 |阅读模式

[其他]CS 61B Data Structures(in Java) #2 - 2014-05-13@Berkeley

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x

没有找到lab13的帖子,于是自己发一个。比较简单。
Screen Shot 2016-05-05 at 4.54.54 PM.png
Screen Shot 2016-05-05 at 4.55.15 PM.png

评分

1

查看全部评分

DetectiveConan 发表于 2017-3-17 14:05:32 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这道题目粗看不难,但是readme.pdf中有几句提示值得玩味:
Try to think of the fastest, simplest code for length2Paths(). It's possible to do it with a relatively simple triply-nested loop.  ... If your TA thinks your algorithm is too slow, you'll be asked to do it again.
那么问题来了,how to define fastest, simplest code?
我用两种不同的思路来解决这个问题:
(1)use a triply-nested loop with modification.
   INSTEAD OF:
  1. for( int u = 0; u < vertices; u++){
  2.             for(int v = 0; v < vertices; v++) {
  3.                          for(int w = 0; w < vertices; w++){
  4.               // set newGraph.adjMatrix[][].
复制代码
The running time is O(n^3). Thus, we need to improve the performance.
IMPROVEMENT:
  1. //STEP 1: loop through the adjMatrix to determine the degree of each vertex, O(n^2).
  2. //STEP 2:  loop through the adjMatrix to form the incidentEdges for each vertex, O(n^2). (NOTE: incidentEdges[i].length == degree(i)  => save memory.)
  3. //STEP 3:
  4.                    for(int u = 0; u < vertices; u++) {
  5.                          for(int v : incidentEdges[u]) {
  6.                                for(int w : incidentEdges[v]){
  7.                                // set newGraph.adjMatrix[][].
复制代码
The running time is O(n^2 + n * max(degree(i))^2). Faster since degree(i) < n.
This implementation is much intuitive and clear.
(2) use BFS as someone suggested.
STEP1  loop through every vertex.
              STEP1.1   start BFS from this vertex.
              STEP1.2   get all vertices in the LEVEL length and set newGraph.adjMatrix.
The crux of this implementation: how to represent one vertex's LEVEL.
Originally, I used an int array to store the level info and update it according to the preceding vertex's.
However, it is WRONG. Because the same vertex can have the DIFFERENT level number and can COEXIST in the queue under certain circumstances.

For example, in the given test code, when length = 5.
Level       0     1    2    3     4     5
vertex      8->4->2->0->8->4
                   8->4->5->7
                   8->4->5->9->1->0
                   8->4->5->9->1->3
                   8->6->4->2->0->8
                   8->6->4->5->7
                   8->6->4->5->9
                   8->6->7
                   8->10->6->4->2
                   8->10->6->4->5
                   8->10->6->7     
The running time is somewhat complicated, which I am unable to give the analysis.

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

veralavander 发表于 2016-5-14 00:20:53 | 显示全部楼层
关注一亩三分地微博:
Warald
想问一下~~~楼主用的是什么样的算法哇~
回复 支持 反对

使用道具 举报

elyn 发表于 2016-5-20 16:10:34 | 显示全部楼层
交作业。最难的部分竟是理解题意,一直以为if and only if 表示仅仅的意思,但是在这道题里面意思竟然是只要的意思 = =??囧

更多图片 小图 大图
组图打开中,请稍候......
回复 支持 反对

使用道具 举报

elyn 发表于 2016-5-20 16:13:34 | 显示全部楼层
veralavander 发表于 2016-5-14 00:20
想问一下~~~楼主用的是什么样的算法哇~

我用的两重循环内嵌广度优先搜索
回复 支持 反对

使用道具 举报

Sophia_Z 发表于 2016-6-16 18:48:16 | 显示全部楼层
elyn 发表于 2016-5-20 16:13
我用的两重循环内嵌广度优先搜索

所以你是用BFS遍历两遍吗?
我也是用了BFS,但是遍历一遍,起始点我随机生成。然后想问一下你是怎么解决点不完全connected的情况。
比如假如我从第8个点开始进行BFS(题目给的第8行是空,第8个点没有任何chidren结点),那么BFS第一个步骤,enqueue(8)之后进入的那个循环dequeue(8)就会出现队列为空而跳出循环的情况,这样除了第8个点之外的点都没有visited
回复 支持 反对

使用道具 举报

elyn 发表于 2016-6-17 12:49:45 | 显示全部楼层
Sophia_Z 发表于 2016-6-16 18:48
所以你是用BFS遍历两遍吗?
我也是用了BFS,但是遍历一遍,起始点我随机生成。然后想问一下你是怎么解决 ...

我没有看太明白你这个算法。。
我用的是两重循环需要遍历所有点,目前也没有想到更好的办法
第一重是check所有开始点,第二重是check所有结束点。
中间套的是BFS。
回复 支持 反对

使用道具 举报

elyn 发表于 2016-6-17 13:27:47 | 显示全部楼层
Sophia_Z 发表于 2016-6-16 18:48
所以你是用BFS遍历两遍吗?
我也是用了BFS,但是遍历一遍,起始点我随机生成。然后想问一下你是怎么解决 ...

我想了下你的算法,如果只用BFS遍历,可以处理的话,解决完全不连接的点,估计还是需要套一重循环去check所有的点是不是有被处理过?
回复 支持 反对

使用道具 举报

Sophia_Z 发表于 2016-6-17 15:28:18 | 显示全部楼层
elyn 发表于 2016-6-17 13:27
我想了下你的算法,如果只用BFS遍历,可以处理的话,解决完全不连接的点,估计还是需要套一重循环去check ...

被发现了。。。我用了一个boolean记录是否全部遍历过。。。好蛋疼的。。把BFS改了一下。。话说你说的check所有开始点和结束点的意思是 每个点都作为开始点 操作一次吗?我有点没明白
回复 支持 反对

使用道具 举报

elyn 发表于 2016-6-17 15:44:56 | 显示全部楼层
是的,第一重循环把每个点作为开始点进行BFS处理,然后第二重循环做为结束点check每个点是不是满足条件。
回复 支持 反对

使用道具 举报

elyn 发表于 2016-6-17 15:45:12 | 显示全部楼层
Sophia_Z 发表于 2016-6-17 15:28
被发现了。。。我用了一个boolean记录是否全部遍历过。。。好蛋疼的。。把BFS改了一下。。话说 ...


是的,第一重循环把每个点作为开始点进行BFS处理,然后第二重循环做为结束点check每个点是不是满足条件
回复 支持 反对

使用道具 举报

elyn 发表于 2016-6-17 16:22:30 | 显示全部楼层
Sophia_Z 发表于 2016-6-17 15:28
被发现了。。。我用了一个boolean记录是否全部遍历过。。。好蛋疼的。。把BFS改了一下。。话说 ...

好囧,原来我的算法也用一重循环就可以了。
把每个点当做开始点BFS,把第N层的点作为结束点,更新到新的G里面就可以了,,,哈哈哈,也不知道当初为什么用了两重循环
回复 支持 反对

使用道具 举报

zzdsg 发表于 2016-8-26 11:18:46 | 显示全部楼层
做完了~开心~来这里打卡
更多图片 小图 大图
组图打开中,请稍候......
回复 支持 反对

使用道具 举报

fishgo 发表于 2016-9-30 01:20:15 | 显示全部楼层
马上就要完成61B了,开心!
更多图片 小图 大图
组图打开中,请稍候......
回复 支持 反对

使用道具 举报

闲的时光 发表于 2016-12-7 15:47:18 | 显示全部楼层
屏幕快照 2016-12-06 下午8.34.40.png 屏幕快照 2016-12-06 下午8.34.50.png 屏幕快照 2016-12-06 下午8.34.57.png
回复 支持 反对

使用道具 举报

codergoose 发表于 2016-12-17 12:13:34 | 显示全部楼层
lab13.png
回复 支持 反对

使用道具 举报

蔚蔚酱 发表于 2017-3-18 22:10:08 | 显示全部楼层
今天终于get到了递归的一种正确打开方式,不能去用回溯的方法理解递归(因为回溯本质上还是在一层层迭代了),而是用数学归纳法理解递归。只要base case成立(n=0,程序对n=1时成立),n=k时,对k+1也成立,那么久永远成立了。
看了楼上的,只有一句膜可以说。。。。
Lab13.PNG
回复 支持 反对

使用道具 举报

mmyn 发表于 2017-5-19 01:44:20 | 显示全部楼层
想要得到正确答案并不难,但是看了楼上各种分析之后感觉自己有点儿嫩了,今天晚了,明天起来看看有没有能改进的地方~
1.png 2.png
回复 支持 反对

使用道具 举报

splansher 发表于 2017-5-29 11:33:36 | 显示全部楼层
elyn 发表于 2016-6-17 16:22
好囧,原来我的算法也用一重循环就可以了。
把每个点当做开始点BFS,把第N层的点作为结束点,更新到新的 ...

你好 。。那个BFS怎么套进去阿。。就是怎么把老师上课的  BFS代码改一下。。。改了好久。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-25 06:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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