🐶onsite遇到一个不会做的题求解

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

只留最远点也需要O(NlogN): https://mukeshiiitm.wordpress.co ... est-pair-of-points/

acerlawson 发表于 2021-5-26 23:41
第一题分块吧， 为了简化题意，我们先假设题目用的是曼哈顿距离，假设距离最小距离为k。

那么我们用边长 ...

删尽可能少的点等价于minimum vertex cover（cover所有距离小于k的边），是NP-complete的

匿名者 发表于 2021-5-26 23:07
能讲一下具体的算法嘛？union find的题我也做过一些，但是想不出来怎么应用到这里

仔细一下ｕｎｉｏｎ　ｆｉｎｄ貌似比　N^2 还慢，不好意思　

fatalme 发表于 2021-5-27 00:48
只留最远点也需要O(NlogN): https://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-poi ...

还是比n^2强啊啊啊啊

text justification 哪有2个follow up?

匿名者 发表于 2021-5-26 23:56
我上来就直接euclidean了没想曼哈顿距离。把小网格边长换成 k*根号2我觉得也行不通吧？比如说k=1，那么(0 ...

应该是 k / 根号2

kazumi 发表于 2021-5-27 01:06
text justification 哪有2个follow up?

follow up在利口上木有，就面试官自个加了一些奇怪的条件（比如：单词长度比行宽要长的时候用小横杠把单词掰开）。都不麻烦，能把那题在lc上写明白的我觉得都不至于答不出来

acerlawson 发表于 2021-5-27 01:09
应该是 k / 根号2

那反过来，k为根号二。现在两个点(0,0),(0,1.3)。按照你的分法，方格就是x=正负1和y=正负1四条线圈起来的部分。那么并不能直接把第二个点排除掉，还是要专门算一下距离的吧。