11.9新鲜google电面

longest increasing value sequence 都变成warm up的题了T^T，第二题通懵逼

lz有消息了吗

vinoblade 发表于 2015-11-10 08:21
不是特别好描述，简单说就是要通过给的IntStream类中的方法来构建新的UnionStream类。要求实现UnionOp， ...

请问一个IntStream类怎么返回A和B两个set呢？是有两个IntSteam吗？

bobzhang2004 发表于 2015-12-6 04:31
请问一个IntStream类怎么返回A和B两个set呢？是有两个IntSteam吗？

初始化的时候初始化两个对象分别返回

写了下UnionSet类欢迎指教

1. public class UnionSet {
   
2. 
   
3.         private IntStream A;
   
4.         private IntStream B;
   
5.         private Integer next;
   
6.         private Integer ANext;
   
7.         private Integer BNext;
   
8.         public UnionSet(int[] Aarr, int[] Barr) {
   
9.                 A = new IntStream(Aarr);
   
10.                 B = new IntStream(Barr);
    
11.                 next = null;
    
12.         }
    
13.        
    
14.         public boolean hasNext() {
    
15.                 if (ANext == null && BNext == null && !A.hasmore() && !B.hasmore() && next == null) {
    
16.                         return false;
    
17.                 }
    
18.                
    
19.                 return true;
    
20.         }
    
21.         public static void main(String[] args) {
    
22.                 int[] Aarr = {1,2,3, 5};
    
23.                 int[] Barr = {1,4,5,6};
    
24.                 UnionSet us = new UnionSet(Aarr, Barr);
    
25.                 while (us.hasNext()) {
    
26.                         System.out.println(us.next());
    
27.                 }
    
28.         }
    
29.        
    
30.         public void unionOp() {
    
31.                 if (next == null) {
    
32.                         if (ANext == null && !A.hasmore()) {
    
33.                                 next = B.next();
    
34.                                 return;
    
35.                         }
    
36.                         if (BNext == null && !B.hasmore()) {
    
37.                                 next = A.next();
    
38.                                 return;
    
39.                         }
    
40.                         if (ANext == null) {
    
41.                                 ANext = A.next();
    
42.                         }
    
43.                         if (BNext == null) {
    
44.                                 BNext = B.next();
    
45.                         }
    
46.                         if (ANext < BNext) {
    
47.                                 next = ANext;
    
48.                                 ANext = null;
    
49.                         } else if (ANext > BNext){
    
50.                                 next = BNext;
    
51.                                 BNext = null;
    
52.                         } else {
    
53.                                 next = ANext;
    
54.                                 ANext = null;
    
55.                                 BNext = null;
    
56.                         }
    
57.                 }
    
58.         }
    
59.        
    
60.         public int next() {
    
61.                 unionOp();
    
62.                 int res = next;
    
63.                 next = null;
    
64.                 return res;
    
65.         }
    
66.        
    
67.         class IntStream {
    
68.                 private int[] arr;
    
69.                 private int pos;
    
70.                 public IntStream(int[] arr) {
    
71.                         this.arr = arr;
    
72.                         pos = 0;
    
73.                 }
    
74.                
    
75.                 public int next() {
    
76.                         return arr[pos++];
    
77.                 }
    
78.                 public boolean hasmore() {
    
79.                         return pos < arr.length;
    
80.                 }
    
81.         }
    
82. }
    

复制代码

vinoblade 发表于 2015-11-10 11:28
想了一下，应该可以先计算所有点连成的线的中点，然后依次判断计算两两中点连成的线是不是symmetry line。 ...

任意一点，只可能与另外n-1个点的莫一个点对称，那么就有n-1可能的line，然后O(n)的时间验证一条line，时间复杂度O(n^2)

yimingzi 发表于 2015-11-10 11:15
所以枚举所有的点..O(n^2)..

同意这个暴力的方法