一亩三分地论坛

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

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

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

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

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

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

查看全部评分

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

使用道具 举报

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了,开心!
更多图片 小图 大图
组图打开中,请稍候......
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 20:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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