[关闭]
@qiezhian 2014-07-03T13:30:25.000000Z 字数 17632 阅读 1850

面试题选

算法

1.和为 n 连续正数序列(数组)

题目:输入一个正数 n,输出所有和为 n 连续正数序列。
例如输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以输出 3 个连续序列 1-5、4-6 和 7-8。
分析:这是网易的一道面试题。假设有m个连续正数序列和为n，则设其第一个元素为x，则序列为x,x+1...x+m-1，其和为
m∗x+(1+2+..+m−1)=m∗x+m∗(m−1)/2=n
所以对于n，求具有m个连续正数序列，首先tmp=n−m∗(m−1)/2，如果tmp为正，且tmp能被m整除，则x=tmp/m，即可得到整个序列。

  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  5. void ContinuousSum( int element );
  7. int main( int argc, char* argv[] )
  8. {
  9.     if( argc <= 1 )
  10.     {
  11.         cout<< "Arguments not enough!"<<endl;
  12.         return 0;
  13.     }
  14.     while( --argc )
  15.     {
  16.         cout<< " The Continuous Sum of "
  17.             << atoi( *++argv )<<" is:"<<endl;
  18.         ContinuousSum( atoi( *argv ) );
  19.     }
  20.     return 0;
  21. }
  22. void ContinuousSum( int element )
  23. {
  24.     int m=2, n;
  25.     int tmp;
  26.     int meta;
  27.     while( ( tmp = m*(m-1)/2 ) 
  28.         && ( meta = element - tmp ) > 0 )
  29.     {
  30.         if( meta%m == 0 )
  31.         {
  32.             n = meta/m;
  33.             for( int i=0; i<m; i++ )
  34.                 cout<< n+i<<" ";
  35.             cout<<endl;
  36.         }
  37.         m++;
  38.     }
  39. }

2.最长递减子序列

题目：求一个数组的最长递减子序列，比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}。
分析：创新工厂笔试题。这是很经典的一个问题，用动态规划解决。假设源数组为A，定义一个辅助数组为B，B[i]表示以A[i]结尾的最长递减序列的长度。举个简单的例子，如果A[i]大于之前的所有元素，那么B[i] = 1。
有了这个辅助数组后，可以推出下面这个递推式子。B[i] = max{B[k] + 1, A[k]>A[i]&&0= A[k]时，A[i]就是前一个元素，递归求解即可。算法的时间复杂度为O(n^2)，网上还有一种解法，复杂度为O(nlogn)。有兴趣的网友可以搜一下，本人水平有限没怎么明白，这里就不引用了。转自：http://blog.csdn.net/wuzhekai1985/article/details/6733505。

  1. /*
  2. Filename: FindLDS.cpp
  3. Function: 求数组的最长递减子序列（可不连续）
  4. Details:
  5. */
  6. #include <iostream>
  7. #include <stdlib.h>
  8. #include <memory.h>
  9. using namespace std;
  11. void FindLDS( int A[], int length );
  12. int Find( int B[], int length );
  14. int main()
  15. {
  16.     int A[] = { 9,5,4,3,2,6,5,3,2,1};
  17.     int length = sizeof( A )/sizeof( int );
  18.     FindLDS( A, length );
  19. }
  20. void FindLDS( int A[], int length )
  21. {
  22.     //分配辅助数组B的空间
  23.     int* B = (int*) malloc( sizeof(int)*length );
  24.     if( !B )
  25.         return;
  26.     B[0] = 1;
  27.     int i=1, k;
  28.     int bMax=0;
  29.     int mLastPos;
  30.     //计算辅助数组B的值
  31.     while( i < length )
  32.     {
  33.         for( k=0; k<i; k++ )
  34.             if( A[k] > A[i] && B[k] > bMax )
  35.                 bMax = B[k];
  36.         B[i] = bMax+1;
  37.         bMax = 0;
  38.         i++;
  39.     }
  40.     //找出B中最大值，它是最长递减子序列的末尾元素
  41.     mLastPos = Find( B, length );
  42.     //辅助数组C是用来标记最终结果的，
  43.     //如果C[i]==1则A[i]是结果中的一个元素
  44.     unsigned char* C = (unsigned char *) malloc( 
  45.             sizeof(unsigned char)*(mLastPos+1) );
  46.     if( !C )
  47.         return ;
  48.     memset( C, 0, mLastPos+1 );
  49.     //对数组C进行标记
  50.     C[ mLastPos ] = 1;
  51.     for( i = mLastPos; i>=0 && k>=0 ; )
  52.     {
  53.         k = i;
  54.         while( --k >= 0 )
  55.             if( B[k] == B[i]-1 && A[k] > A[i] )
  56.             {
  57.                 C[k]=1; i=k; break;
  58.             }
  59.     }
  60.     //输出最长递减子序列
  61.     for( i=0; i<=mLastPos; i++ )
  62.         if( C[i] )
  63.             cout<<A[i]<<" ";
  64.     cout<<endl;
  65. }
  66. int Find( int B[], int length )
  67. {
  68.     if( B==NULL || length<=0 )
  69.         return -1;
  70.     int max=0, index=-1;
  71.     for( int i=0; i<length; i++ )
  72.         if( B[i] > max )
  73.         {
  74.             max = B[i];
  75.             index = i;
  76.         }
  77.     return index;
  78. }

3.链表倒数第K个节点

题目：输入一个链表，输出该链表的第K个节点。为符合多数人习惯，指定链表尾节点为倒数第一个节点。
分析：思路很简单我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
相关题目：求链表中间节点，如果节点总数为奇数，则返回中间节点，为偶数，返回中间两个节点中任意一个。思路就是两个指针，一个走两步，一个走一步，当走得快的到达末尾时，走得慢的就是中间节点。这个函数在下面代码中有实现。
判断一个单向链表是否形成了环形结构，可以定义两个指针，一个走一次一步，一个一次两步，如果走得快的指针走到了链表末尾都没有追上慢指针，则没有环形结构。

  1. /*
  2. Filename: FindKthToTail.cpp
  3. Function: 找出链表倒数第K个节点，找出链表中间节点
  4. Details:
  5. */
  6. #include <iostream>
  7. using namespace std;
  9. struct Node
  10. {
  11.     int m_nElement;
  12.     Node* m_pNext;
  13. };
  14. Node* FindKthToTail( Node* list, int k);
  15. Node* FindMiddle( Node* list );
  16. Node* create_node( int i );
  17. Node* create_list( int length );
  19. int main()
  20. {
  21.     Node* list = create_list( 10 );
  22.     cout<< FindKthToTail( list, 2 )->m_nElement <<endl;
  23.     cout<< FindMiddle( list )->m_nElement <<endl;
  24. }
  26. Node* create_list( int length )
  27. {
  28.     Node* head = NULL;
  29.     Node* tmp;
  30.     for( int i=0; i<length; i++ )
  31.     {
  32.         if( head==NULL )
  33.         {
  34.             head = create_node( i );
  35.             tmp = head;
  36.         }
  37.         else
  38.         {
  39.             tmp->m_pNext = create_node( i );
  40.             tmp = tmp->m_pNext;
  41.         }
  42.     }
  43.     return head;
  44. }
  45. Node* create_node( int i )
  46. {
  47.     Node* tmp = new Node;
  48.     if( tmp==NULL )
  49.         return NULL;
  50.     tmp->m_nElement = i;
  51.     tmp->m_pNext = NULL;
  52.     return tmp;
  53. }
  54. Node* FindKthToTail( Node* list, int k)
  55. {
  56.     if( list==NULL || k==0 )
  57.         return NULL;
  58.     Node *pFirst, *pSecond;
  59.     pFirst = pSecond = list;
  60.     for( int i=1; i<k; i++)
  61.         if( pFirst->m_pNext!=NULL )
  62.             pFirst = pFirst->m_pNext;
  63.         else
  64.             return NULL;
  65.     while( pFirst->m_pNext!=NULL )
  66.     {
  67.         pFirst = pFirst->m_pNext;
  68.         pSecond = pSecond->m_pNext;
  69.     }
  70.     return pSecond;
  71. }
  72. Node* FindMiddle( Node* list )
  73. {
  74.     if( list==NULL )
  75.         return NULL;
  76.     Node *pFirst, *pSecond;
  77.     pFirst = pSecond = list;
  78.     int i=0;
  79.     while( pFirst->m_pNext!=NULL )
  80.     {
  81.         pFirst = pFirst->m_pNext;
  82.         if( i++%2 )
  83.             pSecond = pSecond->m_pNext;
  84.     }
  85.     return pSecond;
  86. }

4.字符串全排列

http://blog.csdn.net/hackbuteer1/article/details/7462447

5.数组中只出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次，请找出这两个只出现一次的数字。要求时间复杂度为Θ(N)，空间复杂度为Θ(1)。
分析：可以先考虑一个更基本的问题：即一个整型数组里除了一个数字之外，其他的数字都出现了两次，找出这个数字。如果能解决这个问题，那么就把数组分成两部分，每部分都有且只含有一个出现一次的数字，其他都出现两次。所以问题分解为两个子问题：1.将数组分成两组，每组有且只含有一个出现一次的数字；2.在子数组里找出所需数字。
先解决第二个问题，基于这样一个事实：两个相同的数字异或的结果为0.所以对数组从头到尾进行异或，相同数字异或为0，最后的异或结果就是只出现一次的数字。
再解决第一个问题，同样基于上述事实:两个数字异或后必然有一位为1，也就是说可以依靠这一位分辨两个不同的数字，也可以依靠这一位是否为1来将数组分成两个子数组，两个不同的数字必然分别在两个子数组中，而重复的数字必然在同一子数组中。

  1. /*
  2. Filename: FindNumsAppearOnce.cpp
  3. Function: 找到整型数组中两个只出现一次的数字，其他数字均出现两次
  4. Details: 
  5. */
  6. #include <iostream>
  7. using namespace std;
  9. void FindNumsAppearOnce( int A[], int length );
  10. int FindFirstBit1( int n );
  11. bool IsBit1( int n, int bitIndex );
  13. int main( )
  14. {
  15.     int A[] = { 1,2,3,4,5,6,4,3,2,1 };
  16.     int length = sizeof(A)/sizeof(int);
  17.     FindNumsAppearOnce( A, length );
  18. }
  20. void FindNumsAppearOnce( int  A[], int length )
  21. {
  22.     int ResultExclusiveOR = 0;
  23.     for( int i=0; i<length; i++ )
  24.         ResultExclusiveOR ^= A[i];
  25.     int index = FindFirstBit1( ResultExclusiveOR );
  26.     int num1=0, num2=0;
  27.     for( int i=0; i<length; i++ )
  28.         if( IsBit1( A[i], index ) )
  29.             num1 ^= A[i];
  30.         else
  31.             num2 ^= A[i];
  32.     cout<<" The numbers appear once are: "<<num1<<" and "<<num2<<endl;
  33. }
  34. /*
  35. 函数功能：找到数字n的从右往左、
  36. 第一个不为0的位的索引，最右边位索引为0，向左递增
  37. */
  38. int FindFirstBit1( int n )
  39. {
  40.     int index = 0;
  41.     while( !( n&1 ) && ( index < 8*sizeof(int) ) )
  42.     {
  43.         n = n>>1;
  44.         index++;
  45.     }
  46.     return index;
  47. }
  48. //函数功能：数字n的第bitIndex位是否为1
  49. bool IsBit1( int n, int bitIndex )
  50. {
  51.     while( bitIndex>0 )
  52.         n = n>>1;
  53.     return ( n & 1 );
  54. }

6.求二叉树节点的最大距离

题目： 我们定义两节点的距离为两节点边的个数，求一棵二叉树中相距最远两节点的距离。
分析： 第一想法是，一棵树的相距最远的两个节点有三种可能：两节点都在左子树，或都在右子树，或一左一右。若是一左一右，则最远距离为两子树深度之和，若是在同侧子树中，则递归求解左右子树的最远节点距离，最后结果取三者最大值。
但递归效率较低，是否有非递归算法？

  1. /*
  2. Filename: LargestDistanceInBintree.cpp
  3. Function: 找到二叉树中相距最远的节点之间距离（边的个数）
  4. Details:
  5. */
  6. #include <iostream>
  7. using namespace std;
  8. #ifndef MAX
  9. #define MAX( x,y ) ( x>y?x:y )
  10. #endif
  11. //二叉树节点定义
  12. struct Node
  13. {
  14.     int m_nElement;
  15.     Node* m_pLeft;
  16.     Node* m_pRight;
  17. };
  18. /*
  19.    函数功能：找出以root为根节点的二叉树中，
  20.    相距最远的节点之间的距离
  21. */
  22. int LargestDistanceInBintree( Node* root );
  23. /*
  24.    函数功能： 找出以root为根节点的二叉树深度，最底层节点深度定义为1
  25. */
  26. int Depth( Node* root );
  27. /*
  28.    函数功能： 创建一棵简单二叉树
  29. */
  30. Node* create_tree( int n );
  31. Node* create_node( int i );
  32. int main( )
  33. {
  34.     Node* root=NULL;
  35.     root = create_tree( 5 );
  36.     cout<<" Largest Distance between nodes in tree is: "
  37.         <<LargestDistanceInBintree( root )<<endl;
  38.     return 1;
  39. }
  40. int Depth( Node *root )
  41. {
  42.     if( root==NULL )
  43.         return 0;
  44.     return MAX( ( Depth(root->m_pLeft)+1 ) ,( Depth(root->m_pRight)+1 ) );
  45. }
  46. int LargestDistanceInBintree( Node* root )
  47. {
  48.     if( root==NULL )
  49.         return 0;
  50.     int LDistance = Depth( root->m_pLeft ) + Depth( root->m_pRight );
  51.     return MAX( 
  52.             (MAX( LargestDistanceInBintree( root->m_pLeft ),
  53.                     LargestDistanceInBintree( root->m_pRight ) )),
  54.             (LDistance) );
  55. }
  56. Node* create_tree( int n )
  57. {
  58.     Node* head = NULL;
  59.     Node* left = NULL;
  60.     Node* right = NULL;
  61.     for( int i=0; i<n; )
  62.     {
  63.         if( head==NULL )
  64.         {
  65.             head = create_node( i++ );
  66.             left = head;
  67.             right = head;
  68.         }
  69.         else
  70.         {
  71.             left->m_pLeft = create_node( i++ );
  72.             right->m_pRight = create_node( i++ );
  73.             left = left->m_pLeft;
  74.             right = right->m_pRight;
  75.         }
  76.     }
  77.     return head;
  78. }
  79. Node* create_node( int i )
  80. {
  81.     Node *tmp = new Node;
  82.     if( !tmp )
  83.         return NULL;
  84.     tmp->m_nElement = i;
  85.     tmp->m_pLeft = tmp->m_pRight = NULL;
  86.     return tmp;
  87. }

7.根据上排给出十个数，在其下排填出对应的十个数

题目： 要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0 在下排出现了6 次，1 在下排出现了2 次，
2 在下排出现了1 次，3 在下排出现了0 次....
以此类推..
分析： 腾讯面试题，竟然要求十分钟内得出结果（吓尿了），想了十分钟也没想出好的方法（太弱了），百度之，找到了一个较好的解法（参考：http://www.cnblogs.com/liketowindy/p/3606351.html）。
思路：
1、先初始化下排数组，使其值都为0。
2、初始化success状态为1，对上排数组进行遍历，获取每个值在下排数组出现的次数。
3、判断出现次数count，如果与下排数组对应值不相等，将count赋值给下排数组，并将success改为0。
4、判断success的值，为1退出整个循环，为0重复步骤2直至success的值为1。
下面的程序对0-n的序列均能得到正确结果，值得一提的是，当n<7时，会出现死循环，即没有正确的结果。个人分析认为，FindNNums()函数最多运行length次即可得到结果，否则即认为出现死循环，没有正确的结果。本题有待于继续完善。

  1. /*
  2. Filename: FindNNums.cpp
  3. Function: 根据上排给出十个数，在其下排填出对应的十个数，
  4.         要求下排的每个数都是先前上排那十个数在下排出现的次数
  5. Details:
  6. */
  7. #include <iostream>
  8. #include <stdlib.h>
  9. #include <memory.h>
  10. using namespace std;
  12. bool FindNNums( int A[], int B[], int length );
  13. int GetFrequency( int element, int B[], int length );
  15. int main()
  16. {
  17.     int A[]={0,1,2,3,4,5,6,7,8,9};
  18.     int length = sizeof(A)/sizeof(int);
  19.     int *B = (int*) malloc( sizeof(int)*length );
  20.     if( B==NULL )
  21.         return 0;
  22.     memset( B, 0, length );
  23.     int loops = 0;
  24.     while( !FindNNums( A, B,length ) )
  25.         if( loops++ > length )
  26.             {
  27.                 loops = -1;
  28.                 break;
  29.             }
  30.     if( loops == -1 )
  31.         cout<<"no result!"<<endl;
  32.     else
  33.         for( int i=0; i<length; i++ )
  34.             cout<<B[i];
  35.     cout<<endl;
  36.     return 1;
  37. }
  38. bool FindNNums(int A [ ],int B [ ],int length)
  39. {
  40.     bool success=1;
  41.     int frequency=0;
  42.     for( int i=0; i<length; i++ )
  43.     {
  44.         frequency = GetFrequency( A[i], B, length );
  45.         if( frequency!=B[i] )
  46.         {
  47.             B[i] = frequency;
  48.             success=0;
  49.         }
  50.     }
  51.     return success;
  52. }
  53. int GetFrequency(int element,int B [ ],int length)
  54. {
  55.     int frequency=0;
  56.     for( int i=0; i<length; i++ )
  57.         if( element == B[i] )
  58.             frequency++;
  59.     return frequency;
  60. }

8.寻找重复元素

题目： 一个大小为n的数组，里面的数都属于范围[0,n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。
分析： Google面试题。主要的难点在于O(1)的时间复杂度（参考：http://blog.csdn.net/morewindows/article/details/8212446）。由于n大小的数组，数值范围也为[0,n-1]，可以利用数组本身做一个哈希表。遍历数组A：如果A[A[i]]>n 则说明A[i]前面出现过，否则令 A[A[i]]+=n。代码如下。

  1. /*
  2. Filename: FindRepeatedNums.cpp
  3. Function: 一个大小为n的数组，里面的数都属于范围[0,n-1]，
  4. 有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。
  5. Details: 
  6. */
  7. #include <iostream>
  8. #include <stdlib.h>
  9. using namespace std;
  11. void FindRepeatedNums( int A[], int length );
  12. int main( )
  13. {
  14.     int A[] = { 0,1,2, 4,5,6,4,6,8,4,9 };
  15.     int length = sizeof(A)/sizeof(int);
  16.     FindRepeatedNums( A, length );
  17. }
  18. void FindRepeatedNums(int A [ ],int length)
  19. {
  20.     int num=-1;
  21.     int realIndex ;
  23.     for( int i=0; i<length; i++ )
  24.         {
  25.             realIndex = A[i] ;
  26.             while( realIndex > length )
  27.                 realIndex -= length;
  28.             if( A[realIndex] > length )
  29.                 cout<< realIndex <<endl;
  30.             A[realIndex] += length;
  31.         }
  32. }

9.左旋转字符串

题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。
分析：http://blog.csdn.net/zhoushuai520/article/details/7703368

  1. /*
  2. Filename: ReverseString.cpp
  3. Function: 定义字符串左旋转操作：把字符串前面的若干个字符
  4. 移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符
  5. 串cdefab。请实现字符串左旋转的函数，要求对长度为n的字符
  6. 串操作的时间复杂度为O(n)，空间复杂度为O(1)。 
  7. Details:
  8. */
  9. #include <iostream>
  10. #include <string.h>
  11. using namespace std;
  12. /*
  13.    函数功能： 反转字符串str中start至end位部分
  14. */
  15. void Rotate( char *str, int start, int end );
  16. /*
  17.    函数功能: 字符串左旋转n位操作，
  18.    可处理n<0的情况，即右旋操作 
  19. */
  20. void ReverseString( char *str, int n );
  22. int main()
  23. {
  24.     char str[] = "abcdefghijklmn";
  25.     ReverseString( str, -3 );
  26.     cout<<str<<endl;
  27. }
  28. void ReverseString( char *str, int n )
  29. {
  30.     int length = strlen( str );
  31.     if( n>0 )
  32.     {
  33.         n = n%length;
  34.         Rotate( str, 0, n-1 );
  35.         Rotate( str, n, length-1 );
  36.         Rotate( str, 0, length-1 );
  37.     }
  38.     else if( n<0 )
  39.     {
  40.         n = (-n)%length;
  41.         ReverseString( str, length-n );
  42.     }
  43. }
  44. void Rotate( char *str, int start, int end )
  45. {
  46.     if( end<=start )
  47.         return;
  48.     int i=start, j=end;
  49.     char tmp;
  50.     while( i<j )
  51.     {
  52.         tmp = str[i];
  53.         str[i] = str[j];
  54.         str[j] = tmp;
  55.         i++; j--;
  56.     }
  57. }

10.反转句子中单词顺序

题目：输入一个英文句子，反转句子单词顺序，但单词内的字母顺序不变，标点符号和普通字符一样处理。
例如"I am a student."反转为"student. a am I"。
分析：是经典的左旋转字符串问题的扩展。首先我们对每个单词进行反转，最后对整个句子进行反转即可。

11.K选择问题

题目：输入N个元素及一个整数K，在N个元素中找出第K小的数。
方案1.直接快速排序，第K个元素即所求。平均时间Θ(NlogN),最坏时间Θ(N2)。
方案2.快速选择，即在快速排序过程中：如果比枢纽元小的元素个数n<=K-1，则所求元素在枢纽元和大于枢纽元的集合中去找，反之同理。也就是快速选择不是对N个元素进行完全排序，而是有方向性的部分排序，直到找到第K小的元素。平均时间Θ(N)，最坏时间Θ(N2)。实践中此方法非常有效。
方案3.在任一时刻，维持一个K个最小元素集合S，接下来读入一个新元素时，将新元素与S中最大元素比较，若小于最大元素则从S中剔除最大元素，并将新元素加入S。如果用堆来实现S，总的时间是Θ(NlogK)。当查找中位数时，即K=N/2时，时间界为Θ(NlogN)。
上述两个方案均会打乱原序列，如果不能打乱，需要一份copy。

  1. /*
  2. Filename: KSelection.cpp
  3. Function: 输入N个元素及一个整数K，在N个元素中找出第K小的数。
  4. Details: 
  5. */
  6. #include <iostream>
  7. #include "heap.hpp"
  8. using namespace std;
  10. int QuickSelectionK( int A[], int length, int K );
  11. int HeapSelectionK( int A[], int length, int K );
  12. void Swap( int *a, int *b );
  13. int main( )
  14. {
  15.     int A[] = { 1,2,3,4,5,6,7,8,9};
  16.     int length = sizeof(A)/sizeof(int);
  17.     int K = 5;
  18.     cout<<QuickSelectionK( A, length, K )<<endl;
  19.     cout<<HeapSelectionK( A, length, K )<<endl;
  20. }
  21. int QuickSelectionK( int A[], int length, int K )
  22. {
  23.     if( A==NULL || length<=0 || K>=length )
  24.         return 0;//error
  25.     int pivot = length/2;
  26.     int i=0, j=length-2;
  27.     swap( A[pivot], A[length-1] );
  28.     while( i<j )
  29.     {
  30.         while( A[i]<A[length-1] )
  31.             i++;
  32.         while( A[j]>A[length-1] )
  33.             j--;
  34.         if( i<j )
  35.             Swap( &A[i], &A[j] );
  36.         else
  37.             break;
  38.     }
  39.     Swap( &A[i], &A[length-1] );
  40.     if( i+1>K )
  41.         return QuickSelectionK( A, i, K );
  42.     else if( i+1<K )
  43.         return QuickSelectionK( A+i+1, length-i-1, K-i-1 );
  44.     else
  45.         return A[i];
  46. }
  47. int HeapSelectionK( int A[], int length, int K )
  48. {
  49.     if( A==NULL || length<=0 || K>=length )
  50.         return 0;//error
  51.     BinaryHeap<int> heap( K,1 );
  52.     for( int i=0; i<K; i++ )
  53.         heap.Insert( A[i] );
  54.     for( int i=K; i<length; i++ )
  55.         if( heap.FindTop() > A[i] )
  56.         {
  57.             heap.DeleteTop();
  58.             heap.Insert( A[i] );
  59.         }
  60.     return ( heap.FindTop() );
  61. }
  62. void Swap( int *a, int *b )
  63. {
  64.     int tmp = *a;
  65.     *a = *b;
  66.     *b = tmp;
  67. }

12.二叉树的镜像(未完成）

题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
分析：递归的方法很简单，如果左右子树均已完成镜像转换，则只要交换左右子树根节点即可。循环的方法是对每个节点依次镜像转换，所以需要对树进行遍历，这里用宽度优先遍历（层序遍历）为佳。循环实现未完成。

  1. /*
  2. Filename: MirrorofBintree.cpp
  3. Function: 
  4. Details:
  5. */
  6. #include <iostream>
  7. using namespace std;
  9. struct Node
  10. {
  11.     int m_nElement;
  12.     Node* m_pLeft;
  13.     Node* m_pRight;
  14. };
  16. Node* create_node( int i );
  17. Node* create_tree( int n );
  18. void MirrorofBintreeRecursively( Node *root );
  19. void PrintTreePreOrderly( Node *root );
  21. int main()
  22. {
  23.     Node* root = NULL;
  24.     root = create_tree( 5 );
  25.     cout<<"The preorderly print of original tree:"<<endl;
  26.     PrintTreePreOrderly( root );
  27.     cout<<"The preorderly print of mirror tree:"<<endl;
  28.     MirrorofBintreeRecursively( root );
  29.     PrintTreePreOrderly( root );
  30. }
  31. void MirrorofBintreeRecursively( Node* root )
  32. {
  33.     if( root==NULL )
  34.         return ;
  35.     Node *tmp=NULL;
  36.     MirrorofBintreeRecursively( root->m_pLeft );
  37.     MirrorofBintreeRecursively( root->m_pRight );
  39.     tmp = root->m_pLeft;
  40.     root->m_pLeft = root->m_pRight;
  41.     root->m_pRight = tmp;
  42. }
  43. Node* create_tree( int n )
  44. {
  45.     Node* head = NULL;
  46.     Node* left = NULL;
  47.     Node* right = NULL;
  48.     for( int i=0; i<n; )
  49.     {
  50.         if( head==NULL )
  51.         {
  52.             head = create_node( i++ );
  53.             left = head;
  54.             right = head;
  55.         }
  56.         else
  57.         {
  58.             left->m_pLeft = create_node( i++ );
  59.             right->m_pRight = create_node( i++ );
  60.             left = left->m_pLeft;
  61.             right = right->m_pRight;
  62.         }
  63.     }
  64.     return head;
  65. }
  66. Node* create_node( int i )
  67. {
  68.     Node *tmp = new Node;
  69.     if( !tmp )
  70.         return NULL;
  71.     tmp->m_nElement = i;
  72.     tmp->m_pLeft = tmp->m_pRight = NULL;
  73.     return tmp;
  74. }
  75. void PrintTreePreOrderly( Node *root )
  76. {
  77.     if( !root )
  78.         return;
  79.     cout<< root->m_nElement << endl;
  80.     PrintTreePreOrderly( root->m_pLeft );
  81.     PrintTreePreOrderly( root->m_pRight );
  82. }

13.在一个字符串中找到第一个只出现一次的字符

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
分析：这道题是2006年google的一道笔试题。构造一张简单的哈希表即可，这里假定输入字符串的字符集为大小写字符总共26个字符，如果有其他字符可扩展。

  1. /*
  2. Filename: FindFirstCharAppearOnce.cpp
  3. Function: 
  4. 在一个字符串中找到第一个只出现一次的字符,
  5. 如输入abaccdeff，则输出b。
  6. Details: 本代码仅假设字符集为a-z，可扩展
  7. */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #define ASCII_LENGTH (26)
  12. char FindFCAO( char *str );
  14. int main()
  15. {
  16.     char str[] = "abcdefgffdegahibgj";
  17.     printf("The first char appear once of string %s is: %c \n",
  18.             str, FindFCAO( str ) );
  19. }
  20. char FindFCAO( char *str )
  21. {
  22.     unsigned char char_hash[ ASCII_LENGTH ];
  23.     memset( char_hash, 0, ASCII_LENGTH );
  24.     int i = 0;
  25.     while( str[i]!='\0' )
  26.         char_hash[ str[i++]-'a' ]++;
  27.     i = 0;
  28.     while( str[i] != '\0' )
  29.         if( char_hash[ str[i]-'a' ] == 1 )
  30.             break;
  31.         else 
  32.             i++;
  33.     return str[i];
  34. }

14.约瑟夫问题

题目：约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
分析： 第一种想法就是循环链表，按规则数，数到第M个就删除节点，从下一个节点接着数，直到只剩一个节点，时间复杂度为Θ(N∗M)，空间复杂度为Θ(N)。当N和M很大的时候，耗时耗力。第二种解法是递推的解法，时间复杂度只为Θ(N)，空间复杂度为Θ(1)。参考http://www.cnblogs.com/EricYang/archive/2009/09/04/1560478.html。
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n。
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式：
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f[i]，程序也是异常简单，可见数学是多么的重要啊！！！

  1. /*
  2. Filename: Josephus.cpp
  3. Function: 求解约瑟夫问题，得到最后一个幸存者编号。
  4. 约瑟夫问题是个有名的问题：N个人围成一圈，
  5. 从第一个开始报数，第M个将被杀掉，最后剩下一个，其余
  6. 人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，
  7. 6，2，3。最后剩下1号。
  8. Details: 
  9. */
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <time.h>
  14. struct Node
  15. {
  16.     int m_nElement;
  17.     Node* m_pNext;
  18. };
  19. Node* create_node( int i );
  20. int JosephusUsingList( int N, int M );
  21. int Josephus( int N, int M );
  22. //输入参数顺序为： N M
  23. int main(int argc, char* argv[])
  24. {
  25.     int M, N;
  26.     if( argc<3 )
  27.     {
  28.         printf("arguments not enough!\n");
  29.         return 0;
  30.     }
  31.     N = atoi(argv[1]);
  32.     M = atoi(argv[2]);
  33.     printf( "N:%d, M:%d \n", N, M );
  34.     JosephusUsingList( N, M );
  35.     Josephus( N, M );
  36.     return 0;
  37. }
  38. int JosephusUsingList(int N, int M )
  39. {
  40.     int i;
  41.     clock_t tStart, tEnd;
  42.     int time;
  43.     Node *pHead,*pNode, *pPre;
  44.     pHead = pNode = pPre = NULL;
  45.     tStart = clock();
  46.     //build the loop list
  47.     for( i=1; i<=N; i++ )
  48.     {
  49.         if( pHead==NULL )
  50.         {
  51.             pHead = create_node( i );
  52.             pNode = pHead;
  53.         }
  54.         else
  55.         {
  56.             pNode->m_pNext = create_node( i );
  57.             pNode = pNode->m_pNext;
  58.         }
  59.     }
  60.     //create a loop list
  61.     pNode->m_pNext = pHead;
  62.     printf("build done!\n");
  63.     //start execuse process
  64.     pPre = pHead;
  65.     pNode = pHead;
  66.     while( pNode!= pNode->m_pNext )
  67.     {
  68.         for( i=0; i<M; i++)
  69.         {
  70.             pPre = pNode;
  71.             pNode = pNode->m_pNext;
  72.         }
  73.         //delete pNode
  74.         printf( "%d \n", pNode->m_nElement );
  75.         pPre->m_pNext = pNode->m_pNext;
  76.         free( pNode );
  77.         pNode = pPre->m_pNext;
  78.     }
  79.     tEnd = clock();
  80.     time = tEnd - tStart;
  81.     printf( "The surviver is %d .\n", pNode->m_nElement );
  82.     printf( "Run time is %d ms.\n",time);
  83.     return pNode->m_nElement;
  84. }
  85. Node* create_node( int i )
  86. {
  87.     Node* tmp = new Node;
  88.     if( tmp==NULL )
  89.         return NULL;
  90.     tmp->m_nElement = i;
  91.     tmp->m_pNext = NULL;
  92.     return tmp;
  93. }
  94. int Josephus( int N, int M )
  95. {
  96.     int num=1;
  97.     for( int i=1; i<N; i++ )
  98.         num = ( num + M ) % N;
  99.     printf("Josephus: %d\n", num );
  100.     return num;
  101. }

15.Fibonacci数列

题目： 输入n，求出Fibonacci数列第n项。f(0)=0,f(1)=1...f(n)=f(n-1)+f(n-2)。规定f(0)为第一项，所以第n项为f(n-1)。
分析： 千万不要用递归去实现，及其糟糕的时间界，因为涉及过多的递归调用会耗费大量的时间，还有可能会产生栈溢出。

  1. /*
  2. Filename: Fibonacci.cpp
  3. Function: 
  4. 输入n，得到Fibonacci数列的第n项,规定f(0)为第一项
  5. f(0)=0,f(1)=1......f(n)=f(n-1)+f(n-2)
  6. Details:
  7. */
  8. #include <iostream>
  9. using namespace std;
  11. int Fibonacci( int n );
  13. int main()
  14. {
  15.     cout<< Fibonacci( 4 )<<endl;
  16.     return 1;
  17. }
  18. int Fibonacci( int n )
  19. {
  20.     if( n==0 )
  21.         return 0;
  22.     else if( n==1 )
  23.         return 1;
  24.     int num1=0, num2=1;
  25.     int result;
  26.     for( int i=1; i<n; i++ )
  27.     {
  28.         result = num1 + num2;
  29.         num1 = num2;
  30.         num2 = result;
  31.     }
  32.     return result;
  33. }

16.字符串转整数

题目：输入一个表示整数的字符串，将字符串转成整数并输出。例如输入"345"，则输出整数345.
分析： 要实现类似于atoi()函数功能。

  1. /*
  2. Filename: StringtoInt.cpp
  3. Function:
  4. Details:
  5. */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. using namespace std;
  11. int StringtoInt( char *str , int *err );
  13. int main( )
  14. {
  15.     char str[] = "-3456";
  16.     int err=0;
  17.     int result = StringtoInt( str, &err );
  18.     if( err )
  19.         printf("This string is not right!\n");
  20.     else
  21.         printf("The corresponding int of this string is: %d.\n",
  22.                 result );
  23.     return err;
  24. }
  25. /*
  26.    函数功能: 第一个字符可以为'+'或'-'表示符号，
  27.    后面必须全部为0-9的数字，不能有其他字符，
  28.    否则认为输入错误，err置1,若str==NULL,err置2
  29. */
  30. int StringtoInt( char *str, int *err )
  31. {
  32.     if( str==NULL )
  33.     {
  34.         *err = 2;
  35.         return 0;
  36.     }
  37.     int result =0;
  38.     int length =0;
  39.     int exp = 1;
  40.     int j = 0;
  41.     if( str[0] == '+' )
  42.         return  StringtoInt( str+1, err );
  43.     else if( str[0] == '-' )
  44.         return ( -StringtoInt( str+1, err) );
  45.     length = strlen( str );
  46.     for( int i=length-1; i>=0; i-- )
  47.     {
  48.         if( str[i]>='0' && str[i]<='9' )
  49.         {
  50.             j = str[i] - '0';
  51.             result += j*exp;
  52.         }
  53.         else
  54.             *err = 1;
  55.         exp *= 10;
  56.     }
  57.     return result;
  58. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注