八八老东家Pinterest

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 860|回复: 15
收起左侧

[算法题] Erect the fence是个典型的凸包问题。。狗这是要往ACM的方向杀过去了么。。

[复制链接] |试试Instant~ |关注本帖
我的人缘0
2011051305 发表于 2017-8-12 13:53:44 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  77% (122)
 
 
22% (35)  踩

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

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

x
转专业的表示好想死 == 顺便来一发 我看到的还不错的凸包问题解释...
https://segmentfault.com/a/1190000000488339


[size=14.6667px]这题如果我被面到.... 那我也就随缘了
[size=14.6667px]

[size=14.6667px]今天解决了拓扑排序的利扣和林口的题。。 我要不要也打个卡呢

评分

参与人数 1大米 +30 收起 理由
nunuh89 + 30

查看全部评分


上一篇:Leetcode 66题目应该如何理解?
下一篇:刷题进阶Tips--分享给那些有刷题经验或工作经验的人
我的人缘0
fentoyal 发表于 2017-8-13 04:59:10 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  91% (350)
 
 
8% (33)  踩
本帖最后由 fentoyal 于 2017-8-13 05:03 编辑
2011051305 发表于 2017-8-13 03:42
您好 请问cg的缩写是? 是前面版上前辈提到的“计算几何”吗? 谢谢!

是的,computational geometry。这个学科基本是个半死不活的学科。创立的很晚,但迅速得到了很多大神的兴趣,投入研究,结果瞬间把所有问题都解决的差不多了。。。没什么深度的学科。
面试按我理解,最基本的一个算法是左测试(判断一个点是否在一个向量左边)是个必须掌握的点,这个能用到N多种场合。比如判断是否是凸多边形啊,算凸包啊,都用。
其它的还有一些简单算法,比如判断一个点是否在多边形内,一个点是否能"看到“一个线段。其它的基本可以肯定不会考到了。
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
fentoyal 发表于 2017-8-13 01:23:33 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  91% (350)
 
 
8% (33)  踩
凸包不是ACM题。你写写试一试,基本是Medium里实现略麻烦级别的而已,如果知道凸包算法,它连LC hard都算不上。计算几何里基础算法而已。
回复

使用道具 举报

我的人缘0
gypcmbczs 发表于 2017-8-12 20:35:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (55)
 
 
11% (7)  踩
貌似普林斯顿的算法I提到过凸包
回复

使用道具 举报

我的人缘0
LeetCodeOJ 发表于 2017-8-12 23:44:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  47% (23)
 
 
52% (25)  踩
因为bar越来越高了
回复

使用道具 举报

我的人缘0
LeetCodeOJ 发表于 2017-8-12 23:46:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  47% (23)
 
 
52% (25)  踩
这道题 我问一个 高中生 他秒答.....
回复

使用道具 举报

我的人缘0
xiaokaneier 发表于 2017-8-13 00:00:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (13)
 
 
18% (3)  踩
凸包问题学过就是easy,没学过让你无中生有想这个,真让你想到解法那我建议直接去读个PhD吧
回复

使用道具 举报

我的人缘0
 楼主| 2011051305 发表于 2017-8-13 03:02:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (122)
 
 
22% (35)  踩
fentoyal 发表于 2017-8-13 01:23
凸包不是ACM题。你写写试一试,基本是Medium里实现略麻烦级别的而已,如果知道凸包算法,它连LC hard都算不 ...

好的前辈!

我今天仔细琢磨一下看能不能把这个题过了(但说实话 第一眼看上去这道题一点思路都没有 还是看了网上题解才意识到的 == 这大概就是成长的过程嘤嘤嘤嘤~~)
回复

使用道具 举报

我的人缘0
ym3fd 发表于 2017-8-13 03:08:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (23)
 
 
4% (1)  踩
cg的知识点还是要补充的 临时想很困难
回复

使用道具 举报

我的人缘0
fentoyal 发表于 2017-8-13 03:19:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (350)
 
 
8% (33)  踩
2011051305 发表于 2017-8-13 03:02
好的前辈!

我今天仔细琢磨一下看能不能把这个题过了(但说实话 第一眼看上去这道题一点思路都没有  ...

哈,我都没意识到lz原来是你,你的这个ID一串数字,太难认了。

评分

参与人数 1大米 +3 收起 理由
2011051305 + 3 终于发现在回复的右下角有个“评分”按钮!.

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| 2011051305 发表于 2017-8-13 03:41:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (122)
 
 
22% (35)  踩
fentoyal 发表于 2017-8-13 03:19
哈,我都没意识到lz原来是你,你的这个ID一串数字,太难认了。

被前辈认出来了 以后不敢在版上造次
回复

使用道具 举报

我的人缘0
 楼主| 2011051305 发表于 2017-8-13 03:42:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (122)
 
 
22% (35)  踩
ym3fd 发表于 2017-8-13 03:08
cg的知识点还是要补充的 临时想很困难

您好 请问cg的缩写是? 是前面版上前辈提到的“计算几何”吗? 谢谢!
回复

使用道具 举报

我的人缘0
staycrazy 发表于 2017-8-13 06:01:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (111)
 
 
5% (6)  踩
凸包算法在算法导论里就有。。。。。
回复

使用道具 举报

我的人缘0
staycrazy 发表于 2017-8-13 06:02:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (111)
 
 
5% (6)  踩
另外大家可能对ACM这三个字母看得太重了。

实际上ACM里面的水题可以很水,就和LC的hard差不多。

而LC的一些题目其实也都是从竞赛题目转化过来的,比如最初150题里面的那个maximum rectangle.

评分

参与人数 1大米 +3 收起 理由
2011051305 + 3 好的 感谢指导!

查看全部评分

回复

使用道具 举报

我的人缘0
ym3fd 发表于 2017-8-13 09:35:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (23)
 
 
4% (1)  踩
2011051305 发表于 2017-8-13 03:42
您好 请问cg的缩写是? 是前面版上前辈提到的“计算几何”吗? 谢谢!

是的. 推荐邓俊辉老师的 计算几何

评分

参与人数 1大米 +3 收起 理由
2011051305 + 3 好的 感谢指导!

查看全部评分

回复

使用道具 举报

我的人缘0
LeetCodeOJ 发表于 2017-8-13 10:58:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  47% (23)
 
 
52% (25)  踩
但是有人这题直接秒杀…
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html





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

custom counter

GMT+8, 2018-7-18 12:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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