一亩三分地论坛

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

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

[HomeWork] Algorithms, Part I (week 3)

[复制链接] |试试Instant~ |关注本帖
vancexu 发表于 2015-2-13 01:39:34 | 显示全部楼层 |阅读模式

[Coursera]Algorithms, Part I #6 - 2015-01-23@Princeton

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

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

x
本帖最后由 vancexu 于 2015-2-13 01:40 编辑

没看到有人post,就自开一贴,一起跟课的朋友们加油!
Fast里面的subsegment真的很trick,看了forum里的讨论才搞定。
高能搬运,相当剧透:
draw the segment only if current point is lower than all the others collinear points


Screen Shot 2015-02-12 at 9.36.31 AM.png





评分

1

查看全部评分

zhoutaiyanghua1 发表于 2015-3-10 11:06:18 | 显示全部楼层
求版主多加分~  o(* ̄▽ ̄*)ゞ

                               
登录/注册后可看大图
回复 支持 0 反对 1

使用道具 举报

gqjapply 发表于 2015-2-13 01:42:39 | 显示全部楼层
的确啊!!那个subsegment弄了超久!!
回复 支持 反对

使用道具 举报

birdor 发表于 2015-2-15 13:43:40 | 显示全部楼层
这周的作业很费时间啊。

Screenshot 2015-02-14 21.35.03.png
回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-2-15 14:18:18 | 显示全部楼层
求问-  wrong order: slope-ascending, y-ascending, x-ascending (but should not depend on x, y)这个问题怎么解决啊?
我Fast是定义了一个hashmap,每次保存一个斜率的数值和这条线上的最后一个点来避免重复,但是time test里的最后一个test老是通不过,求指教。谢谢!
回复 支持 反对

使用道具 举报

 楼主| vancexu 发表于 2015-2-15 16:33:21 | 显示全部楼层
gjxwin 发表于 2015-2-15 14:18
求问-  wrong order: slope-ascending, y-ascending, x-ascending (but should not depend on x, y)这个问 ...

不好意思,没有出现过这个wrong order这个问题,也没有使用hashmap(貌似课程要求没学过的数据结构都不能用)。
我解决permutation是靠最开始的sort by position。解决subsegement也是靠加一句判断point position,就是只有当你现在check的这个点比所有其他共线的点的position都小的时候才画线。
回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-2-16 00:14:36 | 显示全部楼层
交作业了 Screen Shot 2015-02-16 at 00.12.00.png






评分

1

查看全部评分

回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-2-16 00:17:48 | 显示全部楼层
vancexu 发表于 2015-2-15 16:33
不好意思,没有出现过这个wrong order这个问题,也没有使用hashmap(貌似课程要求没学过的数据结构都不能 ...

有一个问题哎,我个人觉得之前不需要排序,但是这样出来的report里出现了莫名奇妙的很多错误。意思是之前必须得Arrays.sort一下,但是我觉得没必要,不懂层主怎么看?
回复 支持 反对

使用道具 举报

 楼主| vancexu 发表于 2015-2-16 08:26:23 | 显示全部楼层
gjxwin 发表于 2015-2-16 00:17
有一个问题哎,我个人觉得之前不需要排序,但是这样出来的report里出现了莫名奇妙的很多错误。意思是之前 ...

题目中要求输出segment要有序的,所以我很自然的想到要在之前sort一下。你是怎么想的,为什么觉得没必要先sort?
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-2-16 13:00:20 | 显示全部楼层
这次作业中的好多东西都是看了网上的才知道的。惭愧。
比如,怎么解决重复画线的问题,我自己所能想到的就是遍历一下之前的点,如果有相等的就不画。然后网上给的做法真的很奇妙。我想不到。当然这种做法有一个很细节的注意点,我们需要提前定义一个pSlope,然后用来暂存i之前的斜率,这个pSlope不能随意初始化,只能初始化为,负无穷,即同一个点。否则就是Bug。因为在再赋值之前,系统会把这个初始值当作是 i 前的斜率,如果和 i 后的斜率正好相等,那么系统就会误解成,i 后的这个斜率在之前已经存在了,就把这条线给遗漏了。我是调试之后才发现的这个问题。所以必须把pSlope设置为一个i 后的斜率不可能到达值,但很明显,斜率的范围涵盖了所有值。所以只能把pSlope设置为即使可以到达,即使i 后面的斜率与这个初始值相等,系统也没有误判。那只可能是 负无穷,即 i后的多个点与 i 点其实是一点,那么他们是不可以画线的。
还有一开始的一个误区,我总以为,一个起点,只能最多有一条线段。所以进入那个画线的分支后就直接break,没进入则,head++,tail++. 脑子犯浑了。
还有之前java基本零基础。提示说 用 Arrays.sort() 来进行排序,一开始真的不懂。
这次作业最大的帮助可能是知道 Comparator怎么用了。然后思考问题的方法。一些很细节的东西只有Debug的时候才能发现。
1.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

18258170717 发表于 2015-2-18 14:30:47 | 显示全部楼层
Week3的作业从65分做到78分做到81分做到100。没有看论坛的提示。提供一种思路是,先把每个点的所有可能的线找出来,然后把这些线存到HashSet里面去,这样就会自己删除那些重复的线,然后再存回来。楼主的思路我再好好参悟一下。

week3

week3
回复 支持 反对

使用道具 举报

18258170717 发表于 2015-2-18 14:55:51 | 显示全部楼层
gjxwin 发表于 2015-2-16 00:17
有一个问题哎,我个人觉得之前不需要排序,但是这样出来的report里出现了莫名奇妙的很多错误。意思是之前 ...

最后你用hashmap解决了吗,我用HashSet的,可以直接避免重复的segment,subsegment其实很好解决的
回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-2-18 15:00:55 | 显示全部楼层
18258170717 发表于 2015-2-18 14:55
最后你用hashmap解决了吗,我用HashSet的,可以直接避免重复的segment,subsegment其实很好解决的

没有,直接按lz的方法很简单,就是不容易想
回复 支持 反对

使用道具 举报

18258170717 发表于 2015-2-18 15:23:25 | 显示全部楼层
gjxwin 发表于 2015-2-18 15:00
没有,直接按lz的方法很简单,就是不容易想

我重新写了个楼主的方法,测试是可以的,但是价格POSITION_ORDER API测试过不了啊
回复 支持 反对

使用道具 举报

zj45499 发表于 2015-2-18 17:28:49 | 显示全部楼层
难度好大.....Brute的时间总是超过...


Screen Shot 2015-02-18 at 4.52.41 PM.jpg
回复 支持 反对

使用道具 举报

18258170717 发表于 2015-2-18 17:43:33 | 显示全部楼层
zj45499 发表于 2015-2-18 17:28
难度好大.....Brute的时间总是超过...

你用了那个POSITION_ORDER吗,知道怎么能过API。。。
回复 支持 反对

使用道具 举报

zj45499 发表于 2015-2-18 17:58:50 | 显示全部楼层
18258170717 发表于 2015-2-18 17:43
你用了那个POSITION_ORDER吗,知道怎么能过API。。。

为什么需要用Position_Order呢?
直接用Arrays.Sort不就可以了么?
回复 支持 反对

使用道具 举报

18258170717 发表于 2015-2-18 18:20:23 | 显示全部楼层
zj45499 发表于 2015-2-18 17:58
为什么需要用Position_Order呢?
直接用Arrays.Sort不就可以了么?

那你怎么消除permutation?lz不是说draw the segment only if current point is lower than all the others collinear points
回复 支持 反对

使用道具 举报

凛冬将至 发表于 2015-2-18 22:42:55 | 显示全部楼层
week3级加学分咧
hw3.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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