谷歌昂賽面經

po一个我写的第1题，欢迎交流！

1. public static int binarySearch(int [] A) {
   
2.     int left = 0;
   
3.     int right = A.length - 1;
   
4.     while (left != right) {
   
5.         int mid = left + (right - left + 1) / 2;
   
6.         if (A[mid] == A[mid - 1]) {
   
7.             if ((mid - left + 1) % 2 == 0) {
   
8.                 left = mid + 1;
   
9.             } else {
   
10.                 right = mid - 2;
    
11.             }
    
12.         } else {
    
13.             if ((mid - left + 1) % 2 == 0) {
    
14.                 right = mid - 1;
    
15.             } else {
    
16.                 left = mid;
    
17.             }
    
18.         }
    
19.     }
    
20.     return left;
    
21. }

复制代码

请问楼主第三题的followup怎么回答的呀？最佳复杂度是logn吗？我感觉可以把座位的安排想象成一个完全二叉树，但是仔细想想发现并不完全勒？

请问有人知道第一题对应lc 数字是多少呀？

frankhong10585 发表于 2018-3-9 22:50
请问有人知道第一题对应lc 数字是多少呀？

我找到了 lc 540

第二题最大的矿坑定义是什么呢？是这个connected component有多少个1，还是Longest Line of Consecutive One in Matrix？
谢谢

请问第三题followup怎么做？没有思路

lz运气很好啊，都是典型题

楼主第五题面试官要求用trie写了么？

恭喜楼主沾沾喜气

1, 异或整个数组吧？位运算还没开始刷，不知道这个思路对么。2，DFS。3，maxheap，follow up没太明白，比如是第一个人座位是他随便坐么还有第二个人怎么选？之后倒是好说。4，先统计每个字符串出现的次数，然后通过order statistics找出第K frequent的pivot，之后用quick sort的思路，就把前K大和其他的分开了。5，第五题题意不太明白？