现在的位置: 首页 > 综合 > 正文

（转）经典面试题

2018年04月04日 ⁄ 综合 ⁄ 共 24899字 ⁄ 字号 小 中 大 ⁄ 评论关闭

1.        有一个整数数组，请求出两两之差绝对值最小的值。记住，只要得出最小值即可，不需要求出是哪两个数。（Microsoft） 

方法1：两两作差求绝对值，并取最小，O( n2 )。

方法2：排序，相邻两点作差求绝对值，并取最小，O( nlgn ).

方法3：有没有O( n )的解法？网上有如下解法：

设数组A = { a1, a2, … , an }, 求 s = min( |ai - aj| ), 其中1<= i, j <=n.

设B = { b1, b2, … , bn-1 }, 且 bi = ai – ai+1

即：b1 = a1 – a2, b2 = a2 – a3, b3 = a3 – a4, …

 

于是有如下规律：

例如：a3 – a5 = ( a3 – a4 ) + ( a4 – a5 ) =b3 + b4

a1 – a6 = b1 + b2 + … + b5

即：ai – aj = bi + … + bj-1

则数组A中任意两个数的差，都可以用数组B中一个字段的和表示。

则原问题可以转换为：

在数组B中，求连续的某一段，使其和的绝对值最小。（只求最小值，不需要知道具体是哪些数）

例如 B = { 1, -2, 3, -1, -9, 7, -5, 6 }；

则绝对值最小值为0，具体是{ -2, 3, -1 } 或 {3, -1, -9, 7}

 

网上的解法，一般到这里就没下文了。只是简单的提了一下，类似于最大子序列的和。具体怎么做，还要自己想想。

最大子序列和利用DP，可O( n )求解。这题咋做？纠结。

 

2.        写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？） 

据说此题是，Microsoft的大牛只有了4行代码就给出了答案。

可惜，不知道是怎么写的。自己试着写写，当然可能会不至4行。单纯追求行数，也没什么意义，如果你愿意可以把所有的程序都写成一行。

注意：

1. 处理前导空格

2. 处理正负号

3. 处理进制（16进制、8进制、10进制）

4. 非法字符（ 0---9, a---f, A---F）

5. 注意整数的范围，不能溢出 

[cpp] view
plaincopy

  1. bool StrToInt( char *pc, long &value )  
  2. {  
  3.     //去掉前导空格  
  4.     while( ( *pc==' ' || *pc=='\t' ) && *pc != '\0' ) pc++;  
  5.     if( *pc == '\0' )   return false;  
  6.   
  7.     //处理正负号  
  8.     int sign = 1;  
  9.     if( *pc == '+' || *pc == '-' )  
  10.     {  
  11.         if( *(pc+1) =='\0' ) return false;  
  12.         if( *pc == '-' ) sign = -1;   
  13.         pc++;  
  14.     }  
  15.   
  16.     //处理数值  
  17.     long tmp = 0;  
  18.     while( *pc != '\0' )  
  19.     {  
  20.         tmp *= 10;  
  21.         //++优先级比*高  
  22.         if( *pc < '0' && *pc > '9' ) return false;          
  23.         tmp += ( *pc++ - '0' );  
  24.     }  
  25.     value = tmp * sign;  
  26.     return true;  
  27. }  

3.        给出一个函数来输出一个字符串的所有排列 

方法1：

一个简单的DFS。从后往前不断交互。N个字母求全排列，O( n! )。具体实现，看代码吧。

方法2：

如果不会写递归，也可以利用STL。STL里有一个next_permutation函数。利用这个函数可以返回大于原字符串的下一个字典序列。当字符串为最大字典序列时，函数返回false。这样只要先对原字符串排序，然后不断调用next_permuation即可。

[cpp] view
plaincopy

  1. inline void Exchange( char *px, char *py )  
  2. {  
  3.     char tmp = *px;  
  4.     *px = *py;  
  5.     *py = tmp;  
  6. }  
  7.   
  8. void PrintStrPermut( char *pstr, char *pbegin )  
  9. {  
  10.     //处理空字符串  
  11.     if( pstr == NULL || pbegin == NULL ) return;  
  12.   
  13.     //递归终止条件  
  14.     if( *pbegin == '\0' )  
  15.         cout << pstr << endl;  
  16.     else  
  17.     {  
  18.         for( char *p=pbegin; *p!='\0'; p++ )  
  19.         {  
  20.             Exchange( p, pbegin );  
  21.             PrintStrPermut( pstr, pbegin+1 );  
  22.             Exchange( p, pbegin );  
  23.         }  
  24.     }  
  25. }  
  26.   
  27. void PrintStrPermut2( char *pstr )  
  28. {  
  29.     char *p = pstr;  
  30.     while( *p != '\0' ) p++;  
  31.   
  32.     sort( pstr, p );  
  33.     cout << pstr << endl;  
  34.     while( next_permutation( pstr, p ) )  
  35.     {  
  36.         cout << pstr << endl;  
  37.     }  
  38. }  

4．请编写实现malloc()内存分配函数功能一样的代码  

这题比较难，要是不懂点OS的内存管理，根本就无从下手。

我们知道调用malloc()后，OS就要想方设法为我们返回一块空闲空间。这就涉及到OS的内存管理。OS的内存管理可以这样考虑：

假设整块内存有128K

初始状态，128K都是空闲

第一次请求，申请了16k，空闲112K

第二次请求，申请了32K，空闲80K

第三次请求，申请了8K，空闲72K

第二次请求申请的32K被释放，空闲108K

第四次请求，申请了24K，空闲84K

…

从上面的例子可以看出，一整块连续的空闲内存块，经过一段时间的使用，会被无情的划分为许多小块。这些小块大小不等，并且有的空闲、有的被占用。

当调用malloc时，OS就沿内存扫描，找到一块够大的空闲块，从中划分出要使用的部分，将这部分标记为己分配，并返回这部分的首地址。如果，空闲的块都是些小的碎片，那就悲具了（当然，OS可以把将相邻的空闲块合并，再尝试）。

 

现在，模拟一下malloc的过程：

为了便于管理，首先定义内存控制块mcb。这个mcb记录两个信息：块是否空闲、块的大小。即，每个分配出去的块，其实都带有一个mcb，只不过这个mcb位于块的最前端，返回该用户的指针刚好指向mcb之后，所以对用户是不可见的。

现在，就可以处理free了。Free只要把已分配的内存块重新标记为空闲即可，这里当然要用到该快的mcb了。

Malloc简单来说，就是维护几个指针，根据分配请求修改指针位置。对于要分配的块，将标记置位己分配，并返回这部分的首地址。

参考http://lklkdawei.blog.163.com/blog/static/32574109200881445518891/，这里讲的很清楚，还附有代码，我就不狗尾续貂了。

5. 字符串A的后几个字节和字符串B的前几个字节重叠。 

这题似乎没什么玄机，就是个简单的字符串处理。使用strlen和memcpy可以完成，见代码。 

[cpp] view
plaincopy

  1. bool StrOverlap( char *strA, char *strB, int cnt, char *strC )  
  2. {  
  3.      int sizeA = (int)strlen( strA );  
  4.      int sizeB = (int)strlen( strB );  
  5.   
  6.      if( cnt > sizeA || cnt > sizeB ) return false;  
  7.   
  8.      memcpy( strC, strA, sizeA-cnt );  
  9.      memcpy( strC+sizeA-cnt, strB+cnt, sizeB-cnt );  
  10.   
  11.      //注意添加结束标记  
  12.      strC[sizeA+sizeB-2*cnt] = '\0';  
  13.      return true;  
  14. }  

6. 怎样编写一个程序，把一个有序整数数组放到二叉树中？ 

由数组建立排序二叉树。因为数组已排序，所以可以进行类似排序二叉树上的查找。感觉有点类似先序遍历，每次先处理根节点，然后分别是左子树、右子树。具体做法是：

1.整个数组对应一个二叉树，则中间元素对应二叉树的根节点

2.中间元素左边的部分对应左子树、右边的部分对应右子树

3.对左右两部分再继续递归调用。 

[cpp] view
plaincopy

  1. struct BiTreeNode   
  2. {  
  3.     int data;  
  4.     BiTreeNode* leftChild;  
  5.     BiTreeNode* rightChild;  
  6.   
  7.     //构造函数，初始化成员变量  
  8.     BiTreeNode(): data(0), leftChild(0), rightChild(0){};  
  9. };  
  10.   
  11. void ArrayToTree( int *pi, int left, int right, BiTreeNode *&root )  
  12. {  
  13.     if( left <= right )  
  14.     {  
  15.         int mid = ( left + right ) / 2;  
  16.         root = new BiTreeNode;  
  17.         root->data = pi[mid];  
  18.   
  19.         ArrayToTree( pi, left, mid-1, root->leftChild );  
  20.         ArrayToTree( pi, mid+1, right, root->rightChild );  
  21.     }     
  22. }  

7. 怎样从顶部开始逐层打印二叉树结点数据？请编程。 

用队列容易实现。网上有人说有非队列的实现，不过还是用指针把每一层的点都连了起来，然后逐层打印。这种方法和用队列把每层的节点存起来大同小异。

[cpp] view
plaincopy

  1. void PrintTreeByLevel( BiTreeNode *&root )  
  2. {  
  3.     if( root != NULL )  
  4.     {  
  5.         queue<BiTreeNode> que;  
  6.         que.push( *root );  
  7.   
  8.         while( !que.empty() )  
  9.         {  
  10.             BiTreeNode curNode = que.front();  
  11.             que.pop();  
  12.             cout << curNode.data << " ";  
  13.               
  14.             if( curNode.leftChild != NULL ) que.push( *curNode.leftChild );  
  15.             if( curNode.rightChild != NULL ) que.push( *curNode.rightChild );  
  16.         }  
  17.     }     
  18. }  

8.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？ 

这题主要看有没有额外存储空间的限制。

如果没有，可以重新生成一个链表，该链表是原链表的反序。具体做的时候，每次只需把新节点插入的头结点的前面即可。此时，空间复杂度O(n).

如果有存储空间的限制，要求为O(1)，即只能用常数个辅助变量。这时可以用三个指针来实现。首先，需要一个指针cur，指向要反向的节点。因为链表反序，指针要指向前一个，而单链表无法直接得到前一个，所以需要一个指针pre。然后，当指针cur反向后，就无法指向下一个，所以需要一个指针next，用于保存cur的下一个。这样只要遍历整个链表，不断使指针cur所指节点反向即可。 

[cpp] view
plaincopy

  1. struct ListNode  
  2. {  
  3.     int data;  
  4.     ListNode *next;  
  5.   
  6.     ListNode(): data(0), next(0) {};  
  7. };  
  8.   
  9. //假设没有哨兵元素  
  10. ListNode* ReverseList( ListNode *head )  
  11. {  
  12.     //空链表   
  13.     if( head == NULL ) return NULL;  
  14.   
  15.     //只有一个元素的链表  
  16.     if( head->next == NULL ) return head;  
  17.   
  18.     //至少有两个元素  
  19.     ListNode *pre, *cur, *next;  
  20.     pre = head;  
  21.     cur = pre->next;   
  22.     next = NULL;  
  23.   
  24.     while( cur != NULL )  
  25.     {  
  26.         //保存下一个节点的指针  
  27.         next = cur->next;  
  28.   
  29.         cur->next = pre;  
  30.         pre = cur;  
  31.         cur = next;  
  32.     }     
  33.     head->next = NULL;  
  34.     head = pre;  
  35.     return head;  
  36. }  

 

9.请编写能直接实现int atoi(const char * pstr)函数功能的代码。 

需要注意的问题：

1.前导白空

2.正负号

3.不同进制

4.非法字符

5.Int范围 

[cpp] view
plaincopy

  1. int MyAtoi(const char * pstr)  
  2. {  
  3.     //去除前导空格  
  4.     while( *pstr == ' ' || *pstr == '\t' ) pstr++;  
  5.   
  6.     //判断正负号  
  7.     int sign = 1;  
  8.     if( *pstr == '+' || *pstr == '-' )  
  9.     {  
  10.         if( *pstr == '-' ) sign = -1;  
  11.         pstr++;  
  12.     }  
  13.   
  14.     //判断进制  
  15.     int base = 10;  
  16.     if( *pstr == '0' )  
  17.     {  
  18.         pstr++;  
  19.   
  20.         //以0开头的为八进制  
  21.         base = 8;  
  22.         //以0x开头的为16进制  
  23.         if( *pstr == 'X' || *pstr == 'x' )  
  24.         {  
  25.             base = 16;  
  26.             pstr++;  
  27.         }  
  28.     }  
  29.   
  30.     //处理数值部分，注意非法字符  
  31.     long value = 0;  
  32.     while( *pstr != '\0' )  
  33.     {  
  34.         if( base == 10 && ( *pstr < '0' || *pstr > '9' ) ||  
  35.             base == 8 && ( *pstr < '0' || *pstr > '7' ) ||  
  36.             base == 16 && !( ( *pstr >= '0' && *pstr <= '9' ) ||   
  37.                              ( *pstr >= 'A' && *pstr <= 'F' ) ||    
  38.                              ( *pstr >= 'a' && *pstr <= 'f' ) )  
  39.            )   
  40.            return 0;          
  41.   
  42.          value *= base;  
  43.   
  44.          if( base == 16 )  
  45.          {  
  46.              if( *pstr >= '0' && *pstr <= '9' ) value += ( *pstr - '0' );  
  47.              if( *pstr >= 'a' && *pstr <= 'f' ) value += ( *pstr - 'a' ) + 10;  
  48.              if( *pstr >= 'A' && *pstr <= 'F' ) value += ( *pstr - 'A' ) + 10;  
  49.          }  
  50.          else  
  51.          {  
  52.              value += *pstr - '0';  
  53.          }  
  54.          pstr++;  
  55.     }  
  56.          //判断是否溢出  
  57.     if( value > INT_MAX || value < INT_MIN ) return 0;  
  58.       
  59.     return value * sign;  
  60. }  

 

10.编程实现两个正整数的除法，当然不能用除法操作符。

// return x/y.

int div(const int x, const int y)

{

  ....

}

 

a/b=x, 即求a里面有多少个b.

方法一：枚举，b*1，b*2，b*3，…，直到b*x == a 或 b*x < a && b*(x+1) > a，复杂度O( a/b)这样

方法二：

除了x = 1+…+1（x个1相加），x还可以用2的幂的和表示（如4 = 2^2, 7 = 2^2+2+1 ）。不用逐一枚举，类似折半查找。不断划分区间，用区间比较。

不断尝试b*(1<<0)，b*(1<<1)，b*(1<<2)，…，

直到b*(1<<m) < a && b*(1<<m+1) > a，

则从a - b*(1<<m)，然后再重新开始。 

[cpp] view
plaincopy

  1. int Div( const int x, const int y )  
  2. {  
  3.     if( x < y ) return 0;  
  4.   
  5.     int tmp = x;  
  6.     int ans = 0;      
  7.   
  8.     while( tmp >= y )  
  9.     {  
  10.         int cnt = 1;  
  11.         while( ( y * cnt ) <= tmp )  cnt <<= 1;  
  12.           
  13.         cnt >>= 1;  
  14.         ans += cnt;  
  15.         tmp -= y * cnt;  
  16.     }  
  17.     return ans;  
  18. }  

 

11.在排序数组中，找出给定数字的出现次数。比如[1, 2, 2, 2, 3] 中的出现次数是次。 

方法一：直接遍历，首先找到这个数，然后逐一计数，O(n)可完成。

方法二：二分查找，首先找到这个数的第一个，记录其位置。再二分查找，找到这个数的最后一个，记录其位置。最后下边相减，O(lgn)可完成。虽然两次都是二分查找，但还是略微有点区别。

LowerSearch把相等的情况划归到左半部分，所以计算mid时要向下取整。

UpperSearch把相等的情况划归到右半部分，所以计算mid时要向上取整。 

[cpp] view
plaincopy

  1. //target出现的第一个位置  
  2. int LowerSearch( int *pi, int left, int right, int target )  
  3. {     
  4.     while( left < right )  
  5.     {  
  6.         //mid向下取整  
  7.         int mid = ( left + right ) / 2;  
  8.   
  9.         if( target <= pi[mid] )  
  10.         {  
  11.             right = mid;  
  12.         }  
  13.         else  
  14.         {  
  15.             left = mid + 1;  
  16.         }  
  17.     }  
  18.     return left;  
  19. }  
  20. //target出现的第最后一个位置  
  21. int UpperSearch( int *pi, int left, int right, int target )  
  22. {  
  23.     while( left < right )  
  24.     {  
  25.         //这里mid向上取整  
  26.         int mid = ( left + right + 1 ) / 2;  
  27.   
  28.         if( target >= pi[mid] )  
  29.         {  
  30.             left = mid;  
  31.         }  
  32.         else  
  33.         {  
  34.             right = mid - 1;  
  35.         }         
  36.     }  
  37.     return left;  
  38. }  
  39.   
  40. int GetCount( int *pi, int left, int right, int target )  
  41. {  
  42.     int first = LowerSearch( pi, left, right, target );  
  43.     int second = UpperSearch( pi, left, right, target );  
  44.   
  45.     return second-first+1;  
  46. }  

12.平面上N个点，每两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。 

按照一般的方法，逐个求斜率比较，O(n^2)可完成。有没有更快的方法？有。

对所有的点按x坐标排序，然后只比较相邻两点的斜率即可。复杂度O( nlgn )。当然，只要有了算法，编程实现很容易，关键是为什么？

我不会严格的证明，只能朴素的理解一下。

设有三个点A、B、C

如果A、B、C在一条直线上，则斜率相等

如果A、B、C不在一条直线上，则构成三角形ABC。不妨设Xa < Xb < Xc

即按照x坐标排序后，A、B相邻，B、C相邻。也就是说，三角形中AC为最长边。如图，显然Kab和Kbc中至少有个大于Kac.

 

13.一个整数数列，元素取值可能是~65535中的任意一个数，相同数值不会重复出现。是例外，可以反复出现。

请设计一个算法，当你从该数列中随意选取个数值，判断这个数值是否连续相邻。

注意：

- 5个数值允许是乱序的。比如：8 7 5 0 6

- 0可以通配任意数值。比如：7 5 0 6 中的可以通配成或者

- 0可以多次出现。

- 复杂度如果是O(n2)则不得分。

 

首先对这5个数进行排序。

如果5个数中没有0，那么用最大值 – 最小值。如果差值= 4，则连续。否则，不连续。

如果5个数中有0，则0必然排在最前面。依旧最大值 – 最小值。当差值取1，说明只有2个非0数，必然连续，则其余的数都可用0补齐。那么在连续的情况下差值最大取多少？最大值为4。这时必然有一个数不连续，但是可以用0补.

综上：

1.      先排序

2.      用非零最大值 - 非零最小值，如果差值<=4，则连续。否则，不连续。

3.      处理没有非零最大值或非零最小值的情况。

A.      全为零，必连续  B. 只用一个非0值，也连续 

14.设计一个算法，找出二叉树上任意两个结点的最近共同父结点。复杂度如果是O(n2)则不得分。 

       经典的LCA问题，有非常成熟的解法，用tarjan算法或转换为RMQ问题。Tarjan自己没写过。这里是RMQ的解法。对于RMQ也有多种解法，比如线段树、ST等。这里讨论一下ST算法。

RMQ问题：RMQ( A, i, j )表示在数组A中求A[i]…A[j]之间最小值的下标。 

 

        首先，把LCA转换为RMQ问题。

        对二叉树进行DFS，记录每个节点被访问的顺序。因为有回溯，除了根节点，每个节点都被访问2次。设二叉树有n个节点，则DFS完成后回记录2n-1个节点，然后由这些节点构成数组path，该数字记录了DFS遍历节点的顺序。

       在进行DFS时，同时记录各节点的层数，组成数组level。

       对二叉树上的任意两点x和y, 找到x 、y在数组path中第一次出现的位置，记为pos(x), pos(y)。则path[ pos(x) ]…path[ pos(y) ]代表在二叉树上从x遍历到y的一条路径，那么该路径上level最小的点就是x 、y的LCA。

即LCA( A, i, j ) = RMQ( level, pos(x), pos(y) )

 

       RMQ问题的ST求解。ST，实质上属于DP。

定义：dp[i][j]表示数字A中，A[i]…A[i+2^j-1]中（即由A[i]开始的连续2^j个元素）最小值的下标

状态转换方程：dp[i][j] = Min( dp[i][j-1], dp[i+2^(j-1)][j-1] );

大概解释一下：状态方程把A[i]…A[i+2^j-1]共2^j个元素，分成两部分A[i]…A[i+2^(j-1)-1]和A[[i+2^(j-1)]…A[j]，每部分2^( j-1 )个元素，然后取两部分的最小值即可。

       上述部分，其实就是个DP的预处理过程。完成了预处理，最后就是RMQ问题的求解, RMQ( A, i, j ) = ?

       有了上述的dp[][]，只要想办法把A[i]…A[j]分成两部分，使每部分的长度为2^k。这样就可以查dp[][]数组了。对于这两部分有什么要求吗？两部分合起来刚好覆盖整个[ i, j ]区间，这当然是最好的了。但是，有时很难取到整数，所以连部分通常是交叉的，甚至每一部分几乎覆盖了整个区间。

即，2^k = j - i + 1，则可求 k=lg( j-i+1 )。k是下取整。

最终：RMQ( A, i, j ) = Min( dp[i][k], dp[j-2^k+1][j] )

RMQ的ST求解见代码

[cpp] view
plaincopy

  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. const int MAX = 100;  
  5.   
  6. //dp[i][j] 表示从i开始到为i+2^j -1中值最小的一个值（从i开始2^j个数）  
  7. //dp[i][j] = min( dp[i][j-1], dp[i+2^(j-1)][j-1] );  
  8. //查询RMQ( i, j )  
  9. //将i,j分成两个2^k个区间  
  10. //k = log2( j - i + 1 )  
  11. //查询结果 min( dp[i][k], dp[j-2^k+1][k] )  
  12. int dp[MAX][MAX];  
  13.   
  14. inline int Min( int x, int y )  
  15. {  
  16.     return x < y ? x : y;  
  17. }  
  18.   
  19. //使用DP，建立查询表  
  20. void MakeRmqIndex( int *data, int size )  
  21. {  
  22.     int i, j;  
  23.     for( i=0; i<size; i++ )  
  24.     {  
  25.         dp[i][0] = i;  
  26.     }  
  27.     for( j=1; (1<<j)<size; j++ )  
  28.     {  
  29.         for( i=0; i+(1<<j)-1 < size; i++ )  
  30.         {  
  31.             dp[i][j] = data[ dp[i][j-1] ] < data[ dp[i+(1<<(j-1))][j-1] ] ? dp[i][j-1] : dp[i+(1<<(j-1))][j-1];   
  32.         }  
  33.     }  
  34. }  
  35.   
  36. //查表，并返回结果  
  37. int RmqIndex( int begin, int end, int *data )  
  38. {  
  39.     int k = (int)( log( ( end - begin + 1 ) * 1.0 )/ log( 2.0 ) );  
  40.     return data[ dp[begin][k] ] < data[ dp[end-(1<<k)+1][k] ] ? dp[begin][k] : dp[end-(1<<k)+1][k];  
  41. }  
  42.   
  43. int main()  
  44. {     
  45.     int data[10] = { 1, 3, 3, 4, 5, 6, 6, 7, 9, 11 };     
  46.   
  47.     //返回最小索引  
  48.     MakeRmqIndex( data, 10 );  
  49.     cout << RmqIndex( 4, 9, data) << endl;    
  50.     return 0;  
  51. }  

15.一棵排序二叉树，令f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。

 

16. 一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。复杂度最好是O(n)，如果是O(n2)则不得分 

这题要求O(n)，我能想到就是：使用一个有N个元素的数组，然后用数值作为数组的下标，然后遍历数组。

1.正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除，现给定a和b，需要计算出Q中的前几项，

例如，当a=3，b=5，N=6时，序列为3，5，6，9，10，12

(1)、设计一个函数void generate（int a,int b,int N ,int * Q）计算Q的前几项

(2)、设计测试数据来验证函数程序在各种输入下的正确性。

 

感觉有点类似归并排序的Merge。有两个数组A、B。

数组A存放：3*1、3*2、3*3…

数组B存放：5*1、5*2、5*3…

有两个指针 i, j，分别指向A、B的第一个元素。取Min( A[i], B[j] )，并将较小值的指针前移，然后继续比较。

当然，编程实现的时候，完全没有必要申请两个数组，用两个变量就可以。

[cpp] view
plaincopy

  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. void Generate( int a,int b,int N ,int * Q )  
  5. {     
  6.     int tmpA, tmpB;  
  7.     int i = 1;  
  8.     int j = 1;  
  9.   
  10.     for( int k=0; k<N; k++ )  
  11.     {  
  12.         tmpA = a * i;  
  13.         tmpB = b * j;  
  14.   
  15.         if( tmpA <= tmpB )  
  16.         {  
  17.             Q[k] = tmpA;  
  18.             i++;  
  19.         }  
  20.         else  
  21.         {  
  22.             Q[k] = tmpB;  
  23.             j++;  
  24.         }  
  25.     }  
  26. }  
  27.   
  28. int main()  
  29. {  
  30.     int Q[6];  
  31.     Generate( 3, 5, 6 ,Q );  
  32.     return 0;  
  33. }  

2.有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面（大写或小写字母之间不要求保持原来次序），如有可能尽量选择时间和空间效率高的算法c语言函数原型void proc（char *str）

也可以采用你自己熟悉的语言

 

应该类似快排的partition。快排的partition也有两种常见的实现：从左往右扫描、从两头往中间扫描。这里使用从左往后扫描的方式。

字符串在调整的过程中可以分成两个部分：已排好的小写字母部分、待调整的剩余部分。用两个指针i和j，其中i指向待调整的剩余部分的第一个元素，用j指针遍历待调整的部分。当j指向一个小写字母时，交换i和j所指的元素。向前移动i、j，直到字符串末尾。

[cpp] view
plaincopy

  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. void Proc( char *str )  
  5. {  
  6.     int i = 0;  
  7.     int j = 0;  
  8.   
  9.     //移动指针i, 使其指向第一个大写字母  
  10.     while( str[i] != '\0' && str[i] >= 'a' && str[i] <= 'z' ) i++;  
  11.   
  12.     if( str[i] != '\0' )  
  13.     {  
  14.         //指针j遍历未处理的部分，找到第一个小写字母       
  15.         for( j=i; str[j] != '\0'; j++ )  
  16.         {  
  17.             if( str[j] >= 'a' && str[j] <= 'z' )  
  18.             {  
  19.                 char tmp = str[i];  
  20.                 str[i] = str[j];  
  21.                 str[j] = tmp;  
  22.                 i++;                  
  23.             }             
  24.         }  
  25.     }     
  26. }  
  27.   
  28. int main()  
  29. {  
  30.     char data[] = "SONGjianGoodBest";  
  31.     Proc( data );     
  32.     return 0;  
  33. }  

 3.如何随机选取1000个关键字。

给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

 

说实话我不会做，是看网上的答案。感觉是对的，但又说不上为什么。

思路是这样的：

1.申请一个1000个元素的数组，用于保存最后选中的关键字

2.将数据流中前1000个直接放入数组中

3.对于第n个元素（n>1000）, 以1000/n的概率随机替换数组中的一个元素

这个就能保证每个元素都以1000/n的概率被选中。哎，为什么？先放这吧，以后再说。 

4.判断一个自然数是否是某个数的平方。说明：当然不能使用开方运算。 

也就是判断一个自然数是否是完全平方数。

方法一：从1开始逐个尝试，即判断1*1，2*2，3*3…,算法复杂度O( N^0.5 )

方法二：相当于在1…N之间找一个数x，使x*x = N。这样看就是一个查找问题，所以用折半查找。算法复杂度O( logN )。

方法三：使用完全平方数的性质：每个完全平方数都可以表示成一系列奇数的和。

不妨这样简单理解一下：

设x是一个完全平方数，即 x = a^2，所以

a^2 = ( a – 1 +1 )^2 = (a-1)^2 + 2( a – 1 ) + 1

               =( (a-2) + 1 )^2 + 2( a – 1 ) + 1

               =(a-2)^2 + ( 2( a – 2 ) + 1 ) + (2( a – 1 ) + 1 )

即 x = 1 + 3 + 5 + … + (2( a – 1 ) + 1 )

故x可以表示为一系列奇数的和. 

因此判断完全平方数的算法：x – 1 – 3 – 5…即从x中连续不断的减去一个奇数，如果结果可以为0，则x是完全平方数。否则，不是。算法复杂度O(N )，当然由于这里做的全部是减法，可能也回比较快。

5.给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。 

关键是要保证每个数字产生的概率相等。

把能随机生成整数1到5的函数记为R15。

我的想法是：把R15调用6次，然后统计这6次中，某个数字出现的次数。比如，统计1出现的次数。1的次数[0, 6],然后给次数加一，就可以随机生成1到7之间的整数。

网上的解法：首先，调用7次R15。然后，取最大值对应的下标，由这些值构成了一个新数组。然后继续调用R15，直到最后只剩下一个数字。

{ 1，2，3，4，5，6，7 }

 5，3，1，5，2，4，5

{ 1， ， ，4， ， ，7 }

 4， ， ，1， ， ，3

{ 1 } 

6.1024! 末尾有多少个？ 

求末尾0个数，也就是对1024！进行因子分解，求因子中10的个数。在进一步，因子中10的个数，就相当与质因子中2*5的个数。因为质因子5的个数比2少，所以也就是求1024！中质因子5的个数。

1，2，3，…，1024中哪些数都含有质因子5？主要有以下几类：

第一类：5的倍数，1024/5 = 204个

第二类：25的倍数，1024/25 = 40个

第三类：125的倍数，1024/125 = 8个

第四类：625的倍数，1024/625 = 1个

则，总的因子5的个数：204 + 40 + 8 + 1 = 253

当然，为什么加起来就是最后的答案？这个不难，自己想想吧。 

7. 有个海盗，按照等级从5到1排列，最大的海盗有权提议他们如何分享枚金币。

但其他人要对此表决，如果多数反对，那他就会被杀死。

他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？

（提示：有一个海盗能拿到98%的金币）

 

      很有意思的一个题。嘿嘿，不会做，也还是看网上答案的。

      当有5个人时，等级为5的海盗，等级最高，他来分配。分配时要考虑两个问题：利益最大、不被杀死。至于他的分配方案会不会招来杀身之祸，完全取决于其他4个人的反应。所以考虑，4个人的情况。

      当有4个人时，等级为4的海盗，等级最高，他来分配。至于他的分配方案会不会招来杀身之祸，完全取决于其他3个人的反应。所以考虑，3个人的情况。

…

       当有2个人时，等级为2的海盗，等级最高，他来分配。这时他就可以肆无忌惮的分配了。分配方案：100，0。即给自己100枚金币，给等级为1的海盗0枚金币。虽然对等级为1的海盗来说很不公平，但是他反对也没用，因为只有两个人，他占不了大多数。

       再来考虑三个人的问题。当有3个人时，等级为3的海盗，等级最高，他来分配。他只要在前两个人中争取一个人就行。分配方案：99，0，1。这样等级为1的海盗肯定不会反对，因为比2个人的时候分的多。只有等级为2的海盗反对，但是没有用

考虑四个人的情况。分配方案：99，0，1，0。等级为4、2的海盗满意。

五个人的情况。分配方案：98，0，1，0，1。

8.给定一个集合A=[0,1,3,8](该集合中的元素都是在，之间的数字，但未必全部包含)，指定任意一个正整数K，请用A中的元素组成一个大于K的最小正整数。

比如，A=[1,0] K=21 那么输出结构应该为100。

 

首先，计算正整数K的位数。假设k有m位。把用A中的元素组成一个大于K的最小正整数记为x。那么x就有m位或者m+1位。

根据K的最高位，在A中选数字。分两种情况：A中的数字都比k的最高位小、A中至少有一个数字等于大于k的最高位。

1.A中的数字都比k的最高位小，则x有m+1位。这时，只要用A中的数字组成一个m+1位的最小正整数即可。

2.A中至少有一个数字等于大于k的最高位。这时x的最高位就是不小于K最高位的最小数字。然后，用同样的方法继续比较下一位。

编程实现：很烦，写的都想吐血了。

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <algorithm>  
  3. using namespace std;  
  4.   
  5. //target为int值，最多是10位数  
  6. const int MAX_INT_CNT = 20;  
  7.   
  8. int NearestInt( int target, int *data, int size )  
  9. {     
  10.     int ans = 0;  
  11.       
  12.     //计算target的位数  
  13.     int cnt = 0;      
  14.     int tmp = target;  
  15.     while( tmp > 0 )   
  16.     {  
  17.         cnt++;  
  18.         tmp /= 10;  
  19.     }  
  20.   
  21.     //将target转换为字符串  
  22.     char des[MAX_INT_CNT];  
  23.     itoa( target, des , 10 );  
  24.     string strTarget( des );  
  25.   
  26.     //对数组排序  
  27.     sort( data, data+size );  
  28.   
  29.     int flag = 0;     
  30.     int i, j;  
  31.     for( i=0; i<cnt; i++ )  
  32.     {  
  33.         ans *= 10;  
  34.         //遍历数组，找到一个合适的元素  
  35.         for( j=0; j<size && flag==0; j++ )  
  36.         {  
  37.             if( strTarget[i] == data[j] )  
  38.             {                             
  39.                 ans += data[j];  
  40.                 break;                                            
  41.             }  
  42.             if( strTarget[i] < data[j] )  
  43.             {  
  44.                 ans += data[j];  
  45.                 flag = 1;  
  46.                 break;  
  47.             }  
  48.         }  
  49.         if( j >= size ) flag = 2;  
  50.         //flag == 2表示前面的数字都相等，只要后面的多一位就行  
  51.         if( flag == 2 )  
  52.         {  
  53.             if( i == 0 )  
  54.             {  
  55.                 //找到一个非0元素  
  56.                 for( j=0; j<size; j++ )  
  57.                 {  
  58.                     if( data[j] > 0 )break;   
  59.                 }                 
  60.                 ans += data[j];  
  61.             }  
  62.             else   
  63.                 ans += data[0];  
  64.         }         
  65.         //flag == 1表示前面的数字比较大，后面的取最小的数字即可         
  66.         if( flag == 1 ) ans += data[0];   
  67.     }  
  68.     //如果前面的数字都相等  
  69.     if( flag == 2 )  
  70.     {  
  71.         ans *= 10;  
  72.         ans += data[0];  
  73.     }     
  74.     return ans;  
  75. }  
  76.   
  77.   
  78. int main()  
  79. {  
  80.     int data[] = { 0, 1, 3, 8 };  
  81.       
  82.     cout << NearestInt( 21, data, 4 ) << endl;  
  83.     return 0;  
  84. }  

9. 用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。 

基本的字符串操作。应该没有什么问题，比起链表的反转简单多了。

[cpp] view
plaincopy

  1. char* Revert( char *str )  
  2. {  
  3.     if( str != NULL )  
  4.     {  
  5.         char *begin = str;  
  6.         char *end = str;  
  7.         while( *end != '\0' ) end++;  
  8.         end--;  
  9.   
  10.         while( begin != end )  
  11.         {  
  12.             char tmp = *begin;  
  13.             *begin = *end;  
  14.             *end = tmp;  
  15.   
  16.             begin++;  
  17.             end--;  
  18.         }  
  19.     }  
  20.     return str;  
  21. }  

10.用C语言实现函数void * memmove(void*dest, const void *src, size_t n)。memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。 

其实就是自己写一个memcpy函数。注意下面三种情况：

指针为空

两个指针间距过小( 如dest = 10010, src =10020, n = 20 )

void*的转换

[cpp] view
plaincopy

  1. void* Memmove( void *dest, const void *src, size_t n )  
  2. {  
  3.     char *cDest = (char*) dest;  
  4.     char *cSrc = (char*) src;  
  5.       
  6.     assert( cDest != NULL && cSrc != NULL );  
  7.     assert( cDest >= cSrc + n || cSrc >= cDest + n );  
  8.   
  9.     while( n-- )    *cDest++ = *cSrc++;   
  10.     return dest;      
  11. }  

11.有一根厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，同时只能通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。

编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

 

        不知这题是想考什么。

        题目的难点在于：初始状态，蚂蚁的方向任意。因为只有5个蚂蚁，每只蚂蚁的方向只有左、右两种选择，因此5只蚂蚁的初始方向有2^5 = 32种情况。

        没有想到什么好的算法，只能枚举所有情况。对每种情况，模拟蚂蚁的爬杆过程：沿初始方向前进、每秒更新一次蚂蚁的位置、更新完成后进行碰撞检测。当所有蚂蚁都爬出细杆后，就可以得到所需时间。最后，在所有的初始情况下，求最小时间和最大时间。索性数据量很小，时间可以接受。

[cpp] view
plaincopy

  1. const int LEFT = 0;  
  2. const int RIGHT = 1;  
  3.   
  4. //记录每个蚂蚁的初始方向  
  5. int dir[5];  
  6. //记录每个蚂蚁的初始位置  
  7. int pos[5];  
  8. //记录每个蚂蚁是否爬出了细杆  
  9. bool isFinish[5];  
  10.   
  11. void Init( int  i )  
  12. {  
  13.     //初始化蚂蚁的方向  
  14.     int tmp = i;  
  15.     int mask = 0x0001;  
  16.     for( int j=0; j<5; j++ )  
  17.     {  
  18.         dir[j] = ( tmp & mask ) ? RIGHT : LEFT;  
  19.         tmp >>= 1;          
  20.     }  
  21.   
  22.     //初始化蚂蚁的位置  
  23.     pos[0] = 3;  
  24.     pos[1] = 7;  
  25.     pos[2] = 11;  
  26.     pos[3] = 17;  
  27.     pos[4] = 23;  
  28.   
  29.     //初始化蚂蚁的状态标志  
  30.     memset( isFinish, false, sizeof(isFinish) );  
  31. }  
  32.   
  33. void AntTime( int &maxTime, int &minTime )  
  34. {  
  35.     int max = 0;  
  36.     int min = 10000000;  
  37.   
  38.     //依次处理32种情况  
  39.     for( int i=0; i<32; i++ )  
  40.     {  
  41.         Init( i );    
  42.   
  43.         //记录已经爬出细杆的蚂蚁个数  
  44.         int cnt = 0;  
  45.   
  46.         //每秒检测一次  
  47.         int time;         
  48.         for( time=1; ; time++ )  
  49.         {  
  50.             //更新蚂蚁位置  
  51.             for( int j=0; j<5; j++ )  
  52.             {  
  53.                 if( !isFinish[j] )  
  54.                 {  
  55.                     if( dir[j] == LEFT )  
  56.                         pos[j]--;  
  57.                     else  
  58.                         pos[j]++;  
  59.                 }                 
  60.             }  
  61.               
  62.             //检测蚂蚁是否已爬出细杆  
  63.             for( int m=0; m<5; m++ )  
  64.             {  
  65.                 if( !isFinish[m] && ( pos[m] < 0 || pos[m] > 23 ) )  
  66.                 {  
  67.                     isFinish[m] = true;  
  68.                     cnt++;  
  69.                 }  
  70.             }  
  71.   
  72.             //如果所有的蚂蚁都已经爬出细杆，则跳出  
  73.             if( cnt >= 5 ) break;              
  74.               
  75.             //如果相撞，则掉头  
  76.             for( int k=0; k<5; k++ )  
  77.             {  
  78.                 if( !isFinish[k] )  
  79.                 {  
  80.                     if( ( k == 0 && pos[k] == pos[k+1] ) || ( k == 5 && pos[k] == pos[k-1] ) ||  
  81.                         ( ( k > 0 && k < 5 ) && ( pos[k] == pos[k+1] || pos[k] == pos[k-1] ) )  
  82.                       )  
  83.                     {  
  84.                         dir[k] = ( dir == LEFT ) ? RIGHT : LEFT;  
  85.                     }  
  86.                 }                                 
  87.             }  
  88.         }  
  89.   
  90.         if( time > max ) max = time;  
  91.         if( time < min ) min = time;  
  92.     }  
  93.     maxTime = max;  
  94.     minTime = min;  
  95. }  

12.请定义一个宏，比较两个数a、b的大小，不能使用大于、小于、if语句 

这里有两种做法：正数的绝对值等于本身、两数相减判断符号位 

[cpp] view
plaincopy

  1. #define MAX( a, b ) ( fabs( a, b ) == ( (a) - (b) ) ? (a) : (b) )  
  2. #define MMAX( a, b ) ( ( ( (a) - (b) ) & ( 1 << 31 ) ) ? (a) : (b) )  

13.两个数相乘，小数点后位数没有限制，请写一个高精度算法

 

14.有A、B、C、D四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在17分钟内这四个人都过桥？

 

        这题想想不难，就不知道具体编程应该怎么实现，能想到的就是DFS。这里的17分钟应该就是最短时间了。先不管编程实现了，说说具体的思路吧

首先，要到对岸，每次不能只过一个人。因为这个人拿了手电，其他人都过不了。这样，每次过桥，必须两个人。两个人过去，其中一个人再拿了手电回来。那选哪两个人过去，哪个人再回来？当然是时间最小的啦。所以，5分钟的人和10分钟的人结伴过河，这样可以把5分钟的时间淹没在10分钟内，共需10钟就可以完成。在让时间最小的人拿了手电回去，那自然选1分钟的人了。也就是说，1分钟的人必须在5、10之前到达对岸。

         这样，整个过程就是：1、2先到对岸（2Min），2拿了手电返回（2Min），5、10再结伴过桥（10Min），1拿手电返回（1Min），最后1、2结伴过桥（2Min），总共刚好17分钟。 

15.有12个小球,外形相同,其中一个小球的质量与其他11个不同，给一个天平,问如何用3次把这个小球找出来，并且求出这个小球是比其他的轻还是重

 

        很久以前的题了，估计大多数人都见过。类似折半查找的方法，把问题的规模以O( lgn )的速度减小。12---6---3---1。当剩3个时，问题最精妙，这时有三种状态可利用：天平左半、天平右边、不在天平两端。这提示我们，其实27个小桥也可以用这个方法。27---9----3----1，即称3次就可以完成。

        其实，这里可以总结一个规律：( 3^(n-1), 3^n ]内的数都只需n次就可以完成。即，10、11、12、….、27个球都只用3次就可以。

16.在一个文件中有10G 个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可。 

       海量数据处理的问题。10G个数，中位数就是第5G、第5G+1个数。回想一下，一般情况下求中位数的做法：类似于快排的partition，找到一个数，使比它小的数的个数占到总数的一半就行。所以，可以把数值空间分段，然后统计每一段中数据的个数，这样就可以很容易的确定中位数在那一段。找个该段后，数据量已经急剧减小了，剩下的问题就好处理了。这种方法可以说是桶排序的思想，也可以说是hash的思想。下面具体分析一下：

        因为要统计每一段中数据的个数，所以可以用一个unsigned int型。unsigned int一般占4个字节，可以计数到2^32-1，大约是4G。题目中有10G个数，如果有很多数落在同一个段中，unsigned int肯定不够用。所以，这里的计数用要8字节的long long。即，相当于有一个数组，数组是long long性，数组的每一个元素，代表了一个数据段内的数据个数。这个数组有多大？为了充分利用2G内存，数组大小2G/8 = 256M。即，有数组long long cnt[256M].

        假设题目中的10G个数都是4字节的int。如何把这10G个整数，映射到cnt[256M]的数组中。可以使用计算机中的虚拟地址到物理地址的转换。取int的高28位作为数组下标的索引值，这样就可以完成映射。

整个算法的流程：

扫描10G个整数，对每个整数，取高28位，映射到数组的某个元素上

给数组的这个元素加1，表示找到一个属于该数据段的元素

扫描完10G个整数后，数组cnt中就记录了每段中元素的个数

从第一段开始，将元素个数累计，直到值刚好小于5G，则中位数就在该段

这时对10G个整数再扫描一遍，记录该段中每个元素的个数。直至累计到5G即可。 

17..一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数 

方法一：

使用位图。4字节的int，有4G个不同的值。每个值，对应1bit，则共需4G/8 = 512M

内存。初始状态，对512M的位图清零。然后，对这40亿个整数进行统计。如果某个值出现了，那么就把这个值对应的bit置位。最后，扫描位图，找到一个没有被置位的bit即可。

方法二：

分段统计。Long long cnt[512M/8=64M]对应数值空间的64M个数据段。每个数据段包含64个不同值，用一个long long作为这个数据段内的位图，位图占64M*8=512M。

这样扫描一遍40亿个整数后，从数组中找到一个计数小于64的元素，然后查看它的位图，找出未出现的元素。

方法二平均性能应该比方法一快，但它占的内存很恐怖。其实，这两种方法都不是很实际，总共1G的内存，算法就消耗512M甚至1G，那剩下的系统程序怎么办？OS都跑不起来了吧。 

18.腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。

        这应该是道面试题，面试官随口问了一下。主要是看思路吧。

        最简单的想法：直接用STL的set。从某一时刻开始计时，每登陆一个QQ，把它放入set，如果已存则直接打印。直到5min后，就可以over了。下面来简单分析一下算法的负复杂度：

空间复制度：用str存储每个QQ号，假设QQ号有20位，理想情况下每个QQ占20Byte。则5min内的QQ：2w * 60 * 5 = 600w个，需要的存储空间600w * 20byte = 12000w byte = 120M，这样的存储应该可以忍受吧。

时间复杂度：STL的set是用二叉树（更确切的说是：红黑树）实现的，查找效率是O( lgn )，应该还是挺快的吧。

 

        呃，有人说不让用STL。那就自己设计一个数据结构呗。该用什么数据结构呢？想了想，还是继续用树，这里用一个trie tree吧。节点内容包括QQ号、指向子节点的指针（这里有10个，认为QQ由0---9的数字组成）。登陆时间要不要？考虑这样一个问题：是否需要把所有的QQ都保存在内存中？随着时间的增加，登陆的QQ会越来越多，比较好的方法是把长时间不登陆的QQ释放掉。所以需要记录登陆时间，以便于释放长期不登陆的QQ。

[cpp] view
plaincopy

  1. struct TrieNode  
  2. {  
  3.     string qq;  
  4.     int lastLoginTime;  
  5.     TrieNode *next[10];  
  6. };  

我们的trie上的操作主要有两个：查找并插入、删除。也就是说，这颗树是不断动态变化的，我们需要维护它。

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞