11.19 电面一轮和二轮

一轮是个国人面试官 就做了一题 lintcode wood cut. 之前只刷了leetcode没刷li

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

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

极坐标sort 然后binary search 最后没写完。 感觉要黑。

roosterxie 发表于 2015-11-24 03:52
我没说清楚。 这里我说的极坐标的中心点是圆心。 角度最近的点就是距离最近的点。不需要计算距离

不好意思，我还没明白什么意思。
如果A中有两个点（0，1），（1，10），而B中有一个点（0，10）
如果按角度来说（0，1）和（0，10）角度最近（一样），但是明明是（1，10）和（0，10）距离更近啊？

jkingxt 发表于 2015-11-22 14:10
为什么要换成极坐标啊？感觉和极坐标没有什么关系啊？可以解释一下么？

换成极坐标 就可以通过binary search最接近的角度来直接得到最近的点 而不用计算距离再比较。计算距离需要O(a*b),而binary search是O(bloga)+O(aloga) 更快

roosterxie 发表于 2015-11-23 01:15
换成极坐标 就可以通过binary search最接近的角度来直接得到最近的点 而不用计算距离再比较。计算距离需 ...

但是使用极坐标来获得角度最近的点不一定是距离的点啊，还是需要计算距离啊

阿三太阴险了，给这么难的题目.......

为什么要换成极坐标啊？感觉和极坐标没有什么关系啊？可以解释一下么？

jkingxt 发表于 2015-11-23 12:12
但是使用极坐标来获得角度最近的点不一定是距离的点啊，还是需要计算距离啊

我没说清楚。 这里我说的极坐标的中心点是圆心。 角度最近的点就是距离最近的点。不需要计算距离

roosterxie 发表于 2015-11-24 03:52
我没说清楚。 这里我说的极坐标的中心点是圆心。 角度最近的点就是距离最近的点。不需要计算距离

哦哦，好的，那我差不多懂了。谢谢lz说的这么详细

LZ有消息了么？

cherylshang 发表于 2015-11-27 22:50
LZ有消息了么？

挂了 明年再接再厉。