第二次笔试

1.找区间，给定有序数列，找出指定目标的区间,要求复杂度为O(logn)。如[4,5,6,6,7,7,7,7,8,8,8,9,9,9] ,目标7，返回区间是[4,7]

答：肯定应用了中值法，因为复杂度为O(logn)。实现如下

特殊情况就是middle index 对应值是target 值时，min,max不被middle替换而是再检查自己对应的值不是target时，分别+1，-1 以缩小范围直至min,max都对应target找出

退出循环的条件有两个：

1.middle == min 此时区间不能再小了，退出；

2.min，max 都已经找到，退出；

 1 void findRange(int * array,int sz, int target){
 2     int min =0;
 3     int max = sz-1;
 4     while(min<max){
 5         int middle = (min+max)/2;
 6         if(middle == min){
 7             break;
 8         }
 9         if(array[middle]<target) min = middle;
10         else if(array[middle]<target) max = middle;
11         else{
12             if(array[min] != target) min++;
13             if(array[max]!= target) max--;
14             if(array[max] == target&&array[min] == target) break;
15         }
16     }
17     if(array[min] != target) cout << '['<<-1<<','<<1<<']'<<'\n';
18     else cout << '['<<min<<','<<max<<']'<<'\n';
19 }

2.求子集。给出一系列正整数集合求所有子集。如[1,2] -> [ [1] , [2] , [1, 2], [] ]

答：查了一下有两种方法

1.使用递归，实现如下（包括show函数）

 1 void subArray(int* result,int *array,int subTotal,int total)
 2 {    
 3     if(subTotal ==0){
 4         for(int i = 0;i<total;i++){
 5             result[i] = -1;
 6         }
 7     }else{
 8         subArray(result,array,subTotal-1,total);
 9         int count = 1 << (subTotal - 1);
10         for(int i = 0;i<count;i++){
11             for(int j = 0;j<total;j++){
12                 result[(count+i)*total+j] = result[i*total+j];
13             }
14             result[(count+i)*total +subTotal-1] = array[subTotal-1];
15         }
16     }
17 }
18 
19 void showArray(int* array, int subTotal,int total){
20     int x = -1;
21     bool first = false;
22     for(int i = 0;i<total;i++){
23         if (x != i / subTotal)
24         {
25             x = i / subTotal;
26             first = true;
27         }
28 
29         int y = i%subTotal;
30         if(y==0){
31             cout<<'[';
32         }
33 
34         if(array[i] != -1){
35             if (!first)
36                 cout << ',';
37             cout<< array[i];
38             first = false;
39         }
40 
41         if (y == subTotal - 1) {
42             cout << ']' << endl;
43         }
44     }
45 }

利用题目条件“正整数”使用“-1” 表示空缺，只用在show函数中将-1 过滤掉就行了

2.使用二进制。所有的数在子集中只有两种状态：在->1，不在->0，就可以简单的使用+1，求出所有子集。实现如下

 1 void allSubArray(int * array, int total){
 2     int subCount = 1<<total;
 3     for(int i= 0;i<subCount;i++){
 4         int subArray[total];
 5         int subPos = 0;
 6         int mainPos = 0;
 7         int j= i;
 8         while(j!=0){
 9             if(j%2 == 1)
10             {
11                 subArray[subPos++] = array[mainPos];
12             }
13             j = j/2;
14             mainPos++;
15         }
16         showArray(subArray,subPos);
17         cout << endl;
18     }
19 }

二进制位为1，则加入子集，否则不加入，i做为计数，总个数为2^total用左移计算的。showArray函数只是简单的输出函数。

显然二进制法更简单直接，要记住

3.实现简单的map[key] = value.要求满capacity时，覆盖最近不常用的

答：这道题很简单，创造动态二维数组data[capacity][2]，data[i][0] = key, data[i][1] = value，count用于记录当前数组中的有效值个数在get(key) 时，仅在[0,count-1]区间查找，并将找到的data[i] 移动到data[0]，这样只用在需要覆盖时，覆盖data[capacity -1] 就行了。

第二次笔试

推荐阅读