要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 5839|回复: 11
收起左侧

[算法题] [Lintcode]Post Office Problem的O(N^2)时间解法?

[复制链接] |试试Instant~ |关注本帖
我的人缘0
stellari 发表于 2015-7-7 19:45:18 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

x
http://www.lintcode.com/en/problem/post-office-problem/#

Post Office问题:在一条直线上有N个“房子”。现在在直线上找K个“邮局”,使得这N个房子到其最近的邮局的距离之和最短。

这个题的challenge是O(N^2)时间复杂度。想问一下大家有什么比较好的想法没有?

评分

1

查看全部评分


上一篇:求问JavaScript上哪刷题啊?
下一篇:分享一本面试书《Programming Interviews Exposed》
我的人缘0
DK_BurNing 发表于 2015-7-11 01:14:06 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
我搜到了一个O(2^n) 的解法,http://blog.csdn.net/find_my_dream/article/details/4931222
楼主可以看看,感觉LintCode上Hard题有的确实比较Hard...

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
zhuli19901106 发表于 2015-7-7 21:48:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
都刷到hard难度了,好快~~
我medium快搞定了,等过几天看看能不能做出来
占个位置先
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| stellari 发表于 2015-7-8 18:43:29 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
大家都没刷Hard的题么?我想了一天了,还是没什么思路。
回复 支持 反对

使用道具 举报

我的人缘0
mkcing 发表于 2015-7-11 01:07:25 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
只想到了O(n^3)的算法
回复 支持 反对

使用道具 举报

我的人缘0
mkcing 发表于 2015-7-11 01:07:31 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
只想到了O(n^3)的算法
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| stellari 发表于 2015-7-11 09:09:54 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
DK_BurNing 发表于 2015-7-11 01:14
我搜到了一个O(2^n) 的解法,http://blog.csdn.net/find_my_dream/article/details/4931222。
楼主可以看 ...

多谢多谢!这正是我需要的。利用单调性这个思路太巧妙了。
回复 支持 反对

使用道具 举报

我的人缘0
DK_BurNing 发表于 2015-7-11 20:51:42 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-7-11 09:09
多谢多谢!这正是我需要的。利用单调性这个思路太巧妙了。

不用谢~
回复 支持 反对

使用道具 举报

我的人缘0
mgccl 发表于 2015-7-14 10:17:50 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-7-11 09:09
多谢多谢!这正是我需要的。利用单调性这个思路太巧妙了。

这种matrix叫做monge matrix.
存在一堆有用的研究.
回复 支持 反对

使用道具 举报

我的人缘0
mhwkanon 发表于 2015-8-1 04:24:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主是LC上 Skyline Problem  作者 那位大神么?ID一样
回复 支持 反对

使用道具 举报

我的人缘0
Linzertorte 发表于 2015-10-31 11:55:34 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
四边形不等式吧。acm的经典题
回复 支持 反对

使用道具 举报

我的人缘0
marthew777 发表于 2015-11-2 10:06:50 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
mgccl 发表于 2015-7-14 10:17
这种matrix叫做monge matrix.
存在一堆有用的研究.

都是大神!
哇塞,原来Monge Matrix 是这么用的,最近写作业看到了,总觉得眼熟,翻书真找到了。。
CLRS 110页 Problem 4-6。。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-27 20:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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