10/3Facebook电面

kobe24 发表于 2016-10-3 17:36
fb这题只要返回一个结果  但是LC那题要返回所有的结果  用BFS

确实确实，看了楼上的解释

tanpf5 发表于 2016-10-3 16:56
是，不过就算不是origin也很简单，就是处理稍微麻烦了点

楼主第二题可不可以quick selection啊

gaocan1992 发表于 2016-10-4 09:43
楼主第二题可不可以quick selection啊

用heap一般就足够好了，quick selection感觉有点偏，没去研究

tanpf5 发表于 2016-10-3 17:45
用heap一般就足够好了，quick selection感觉有点偏，没去研究

想了一下quick selection写起来有点麻烦

gaocan1992 发表于 2016-10-3 17:49
想了一下quick selection写起来有点麻烦

1. public Point[] findK(Point[] points, int k) {
   
2.                 Comparator<Point> comparator = new Comparator<Point>() {
   
3.                         public int compare(Point a, Point b) {
   
4.                                 return (int) (getDistance(b) - getDistance(a));
   
5.                         }
   
6.                 };
   
7.                 if (points.length <= k) {
   
8.                         Arrays.sort(points, comparator);
   
9.                         return points;
   
10.                 }
    
11.                 Point[] result = new Point[k];
    
12.                 quickSelection(points, 0, points.length - 1, k);
    
13.                 for (int i = 0; i < k; i++) {
    
14.                         result[i] = points[i];
    
15.                 }
    
16.                 Arrays.sort(result, comparator);
    
17.                 return result;
    
18.         }
    
19. 
    
20.         public void quickSelection(Point[] nums, int left, int right, int k) {
    
21.                 if (left >= right) {
    
22.                         return;
    
23.                 }
    
24.                 int position = partition(nums, left, right);
    
25.                 if (position + 1 == k) {
    
26.                         return;
    
27.                 } else if (position + 1 < k) {
    
28.                         quickSelection(nums, position + 1, right, k);
    
29.                 } else {
    
30.                         quickSelection(nums, left, position - 1, k);
    
31.                 }
    
32.         }
    
33. 
    
34.         public int partition(Point[] nums, int left, int right) {
    
35.                 if (left >= right) {
    
36.                         return left;
    
37.                 }
    
38.                 Point point = nums[left];
    
39.                 while (left < right) {
    
40.                         while (left < right && getDistance(nums[right]) <= getDistance(point)) {
    
41.                                 right--;
    
42.                         }
    
43.                         nums[left] = nums[right];
    
44.                         while (left < right && getDistance(nums[left]) > getDistance(point)) {
    
45.                                 left++;
    
46.                         }
    
47.                         nums[right] = nums[left];
    
48.                 }
    
49.                 nums[left] = point;
    
50.                 return left;
    
51.         }
    
52. 
    
53.         public double getDistance(Point p) {
    
54.                 return p.x * p.x + p.y * p.y;
    
55.         }

复制代码

gaocan1992 发表于 2016-10-4 10:07

有用heap的代码吗？能贴个上来吗？

iPhD 发表于 2016-10-3 18:09
有用heap的代码吗？能贴个上来吗？

heap很简单http://www.jianshu.com/p/807fc0ec0bc3这里面有

问下楼主两题是不是都问了时间空间复杂度？据说这是FB的一贯风格。。。

iPhD 发表于 2016-10-4 10:21
问下楼主两题是不是都问了时间空间复杂度？据说这是FB的一贯风格。。。

这两题时间空间都比较容易计算，都问了。据说有些难以计算的可能会不问

tanpf5 发表于 2016-10-4 08:47
这个方法不错，具体在空间复杂度上比我的方法好

stack 更容易想到一些~
我是用stack记录不匹配的index，然后扫一遍字符串，把这些剔除掉，不知道LZ是怎么做的？