11/09 Google Onsite

那第二题，如果Input 是 "FooBarFab"， 那满不满足 Pattern : "FBF" ？

GatorAM 发表于 2016-1-23 02:54
那第二题，如果Input 是 "FooBarFab"， 那满不满足 Pattern : "FBF" ？

满足 字数...

那就是说input删除一些字母成为pattern就成，对吧？

GatorAM 发表于 2016-1-23 05:54
那就是说input删除一些字母成为pattern就成，对吧？

也可以这么理解吧

Nero_hu 发表于 2016-1-23 06:15
也可以这么理解吧

Thx     

写了最后一题2K WINDOW的代码

1. public class QuickSelect {
   
2. 
   
3.     public static List<Integer> topK(int[] nums, int k) {
   
4.         List<Integer> result = new ArrayList<Integer>();
   
5.         if (nums == null || nums.length < k) return result;
   
6.         int n = nums.length;
   
7.         int i = 0;
   
8.         for ( ; i < k; i++) result.add(nums[i]);
   
9.         while (i < n) {
   
10.             int j = 0;
    
11.             for (; j < k && i + j < n; j++) {
    
12.                 result.add(nums[i + j]);
    
13.             }
    
14.             quickSelect(result, k);
    
15.             i += j;
    
16.         }
    
17.         return result;
    
18.     }
    
19.    
    
20.     private static void quickSelect(List<Integer> list, int k) {
    
21.         selectHelper(list, 0, list.size() - 1, k);
    
22.         List<Integer> rest = new ArrayList<Integer>();
    
23.         for (int i = k; i < list.size(); i++) rest.add(list.get(i));
    
24.         list.removeAll(rest);
    
25.     }
    
26.    
    
27.     private static void selectHelper(List<Integer> list, int start, int end, int k) {
    
28.         int randomIndex = start + (int)(Math.random() * (end - start + 1));
    
29.         swap(list, end, randomIndex);
    
30.         int i = start - 1, j = start, pivot = list.get(end);
    
31.         while (j < end) {
    
32.             if (list.get(j) >= pivot) {
    
33.                 swap(list, ++i, j);
    
34.             }
    
35.             j++;
    
36.         }
    
37.         swap(list, ++i, end);
    
38.         int leftSize = i - start + 1;
    
39.         if (leftSize == k) return;
    
40.         if (leftSize < k) selectHelper(list, i + 1, end, k - leftSize);
    
41.         else selectHelper(list, start, i - 1, k);
    
42.     }
    
43.    
    
44.     private static void swap(List<Integer> list, int i, int j) {
    
45.         int temp = list.get(i);
    
46.         list.set(i, list.get(j));
    
47.         list.set(j, temp);
    
48.     }
    
49.    
    
50.     public static void main(String[] args) {
    
51.         int[] nums = {9,0,3,2,8,1,2,3,4,5,6,7};
    
52.         List<Integer> list = topK(nums, 3);
    
53.         for (int d : list) {
    
54.             System.out.print(d + " ");
    
55.         }
    
56.         System.out.println();
    
57.             
    
58.     }
    
59. }
    

复制代码