G onsite 2015/02/09

请问第四题有什么比较好的方法呢

lklk1986fa 发表于 2015-2-10 15:06
请问第四题有什么比较好的方法呢

可不可以把圆上每个点用与x轴夹角表示，然后对圆外每个点，取其与圆心连线相对于x轴的夹角，找与这个夹角最近的圆上的点（二分查找，因为圆上点也是夹角表示的），算距离，这个就是对于当前圆外点与所有圆上点的距离的最小值了，比较所有圆外点算得的最小值来得到全局最小值，复杂度是O(NLogM), 如果圆外N个点圆上M个点的话

lklk1986fa 发表于 2015-2-10 15:06
请问第四题有什么比较好的方法呢

我想了半天没想出来，然后面试官提醒我用极坐标。假如在圆上的点的list是A，在园外的点的list是B。我想了个办法，把两个list里面的数都放在一个大list里面，叫做C，然后根据他们相对于圆心的弧度排序。然后C，每次找到一个B里面的点，就找到这个点在前面的一个和后面的一个A里面的点，然后比较这两个A里面的点和B里面的点的距离就可以了。这样的话，时间复杂度大约降到O(nlogn)，也就是之前排序的时间复杂度。后面的时间复杂度是O(n).

Primer 发表于 2015-2-10 15:16
可不可以把圆上每个点用与x轴夹角表示，然后对圆外每个点，取其与圆心连线相对于x轴的夹角，找与这个夹角 ...

嗯，咱俩的做法差不多哦~

tianyangche 发表于 2015-2-10 14:51
不知道何为并查集~小弟把这道题看作是一道图题，每个人建一个Person类，里面有他的id，还有一个list，用 ...

好想法！

第二题能不能建一个n*n的boolean matrix, 对于每个pair把相应的两个位置置1，然后用一个visited[] 和BFS的方法 遍历从1到n?
感觉每道题都有意思。
谢谢分享！

YY大帝 发表于 2015-2-10 23:45
好想法！

yangbin009 发表于 2015-2-11 01:59
第二题能不能建一个n*n的boolean matrix, 对于每个pair把相应的两个位置置1，然后用一个visited[] 和BFS的 ...

我觉得可以呀，我用的是邻接表，你用的是邻接矩阵，是图的两种表示方式~

yangbin009 发表于 2015-2-11 01:59
第二题能不能建一个n*n的boolean matrix, 对于每个pair把相应的两个位置置1，然后用一个visited[] 和BFS的 ...

我想的也是这样，转成图问题，我想的是建成adjency list, 正在看楼主的方法

LZ几轮电面拿到的onsite 电面是什么水平的题目啊？ 从内推到电面到onsite分别花了多少时间？
多谢啦！！！