微软、谷歌、百度等公司经典面试100题[第160题]——自己的实现[转]

原文链接：http://blog.csdn.net/v_JULY_v/archive/2011/03/09/6234496.aspx

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

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <cassert>  
  3. #include <ctime>  
  4. #include <iterator>  
  5. using namespace std;  
  6. /************************************************************************/  
  7. /* 函数功能：有一个整数数组，请求出两两之差绝对值最小的值   
  8.     思路：两个for循环，记录每次的最小值,复杂度为o(N) 
  9. */  
  10. /************************************************************************/  
  11. int GetMinDiff(int arr[], int length)  
  12. {  
  13.     assert(length >=2 );  
  14.     int min = abs(arr[1] - arr[0]);  
  15.     for (int i=0; i<length-1; i++)  
  16.     {  
  17.         for (int j=i+1; j<length; j++)  
  18.         {  
  19.             if(abs(arr[j] - arr[i]) < min)  
  20.                 min = abs(arr[j] - arr[i]);  
  21.         }  
  22.     }  
  23.     return min;  
  24. }  
  25. /************************************************************************/  
  26. /* 方法2：先对数组排序（快速排序）,然后求两两差值的最小值，复杂度为O(lgN + N)* / 
  27. /************************************************************************/  
  28. int cmp(const void *a, const void *b)  
  29. {  
  30.     return *(int *)a - *(int *)b;  
  31. }  
  32. int GetMinDiff2(int arr[], int length)  
  33. {  
  34.     qsort(arr, 10, sizeof(arr[0]), cmp);  
  35.     assert(length >= 2);  
  36.     int min = abs(arr[1] - arr[0]);  
  37.     for (int i=3; i<length; i++)  
  38.     {  
  39.         if (abs(arr[i] - arr[i-1]) < min)  
  40.             min = abs(arr[i] - arr[i-1]);  
  41.     }  
  42.     return min;  
  43. }  
  44. int main()  
  45. {  
  46.     int arr[10];  
  47.     srand((unsigned int)time(NULL));  
  48.     for(int i=0; i<10; i++)  
  49.         arr[i] = rand()%100;  
  50.     copy(arr, arr+10, ostream_iterator<int>(cout, " "));  
  51.     cout<<endl;  
  52.     int minDiff = GetMinDiff(arr, 10);  
  53.     cout<<minDiff<<endl;  
  54.     minDiff = GetMinDiff(arr, 10);  
  55.     cout<<minDiff<<endl;  
  56. }  

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

http://blog.csdn.net/cadcisdhht/archive/2011/02/21/6197041.aspx

 

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

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <cassert>  
  3. #include <ctime>  
  4. #include <iterator>  
  5. using namespace std;  
  6. void swap(char *str, int i, int j)  
  7. {  
  8.     char temp = str[i];  
  9.     str[i] = str[j];  
  10.     str[j] = temp;  
  11. }  
  12. /************************************************************************/  
  13. /* 函数功能：递归求全排列                                               */  
  14. /************************************************************************/  
  15. void GetQuanPaiLie(char *str, int current, int length)  
  16. {  
  17.     if(current == length-1)  
  18.         cout<<str<<endl;  
  19.     else  
  20.     {  
  21.         for (int i=current; i<length; i++)  
  22.         {  
  23.             swap(str, current, i);  
  24.             GetQuanPaiLie(str, current+1, length);  
  25.             swap(str, current, i);  
  26.         }  
  27.     }  
  28. }  
  29. int main()  
  30. {  
  31.     char str[] = "abc";  
  32.     GetQuanPaiLie(str, 0, 3);  
  33. }  

 

4、请编写实现malloc()内存分配函数功能一样的代码。 
给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。

http://lklkdawei.blog.163.com/blog/static/32574109200881445518891/

不会做！

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

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

两题的答案下面代码！

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <deque>  
  3. using namespace std;  
  4. struct TNode  
  5. {  
  6.     int element;  
  7.     TNode* left;  
  8.     TNode* right;  
  9.     TNode(int ele = 0, TNode* l = NULL, TNode* t= NULL)  
  10.         :element(ele), left(l), right(t){}  
  11. };  
  12. /************************************************************************/  
  13. /*函数功能：将一个有序整数数组放到二叉树中                              */  
  14. /************************************************************************/  
  15. TNode* ConvertArrayToBinaryTree(int arr[], int current, int legth)  
  16. {  
  17.     TNode *root = NULL;  
  18.     if (current < legth)  
  19.     {  
  20.         root = new TNode(arr[current]);  
  21.         if(2*current + 1 < legth)  
  22.             root->left = ConvertArrayToBinaryTree(arr, 2*current + 1, legth);  
  23.         if(2*current + 2 < legth)  
  24.             root->right = ConvertArrayToBinaryTree(arr, 2*current + 2, legth);  
  25.     }  
  26.     return root;  
  27. }  
  28. /************************************************************************/  
  29. /* 函数功能：从顶部开始逐层打印二叉树结点数据（借助队列实现）           */  
  30. /************************************************************************/  
  31. void levelOutPut(TNode* root)  
  32. {  
  33.     if(root == NULL)  
  34.         return;  
  35.     deque<TNode*> d;  
  36.     d.push_back(root);  
  37.     while(!d.empty())  
  38.     {  
  39.         cout<<d.front()->element<<" ";  
  40.         if(d.front()->left != NULL)  
  41.             d.push_back(d.front()->left);  
  42.         if (d.front()->right != NULL)  
  43.             d.push_back(d.front()->right);  
  44.         d.pop_front();  
  45.     }  
  46. }  
  47. int main()  
  48. {  
  49.     int arr[10];  
  50.     for (int i=0; i<10; i++)  
  51.         arr[i] = i+1;  
  52.       
  53.     TNode *root = ConvertArrayToBinaryTree(arr, 0, sizeof(arr)/sizeof(arr[0]));  
  54.     cout<<"层次输出二叉树:"<<endl;  
  55.     levelOutPut(root);  
  56.     cout<<endl;  
  57. }  

 

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

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <deque>  
  3. using namespace std;  
  4. struct Node  
  5. {  
  6.     int element;  
  7.     Node* pNext;  
  8.     Node(int ele, Node *next = NULL)  
  9.     {  
  10.         element = ele;  
  11.         pNext = next;  
  12.     }  
  13. };  
  14. /************************************************************************/  
  15. /* 函数功能：构建单链表                                                 */  
  16. /************************************************************************/  
  17.  Node* BuildList(int arr[], int length)  
  18.  {  
  19.     Node* head = NULL; //头结点  
  20.     if(length > 0)  
  21.     {  
  22.         head = new Node(arr[0]);  
  23.         Node* curr = head;  
  24.         Node* newNode = NULL; //新创建的节点  
  25.         for (int i=1; i<length; i++)  
  26.         {  
  27.             newNode = new Node(arr[i]);  
  28.             curr->pNext = newNode;  
  29.             curr = newNode;  
  30.         }  
  31.     }  
  32.     return head;  
  33.  }  
  34.  //函数功能：输出单链表  
  35.  void PrintList(Node* head)  
  36.  {  
  37.      Node *temp  = head;  
  38.      while (temp != NULL)  
  39.      {  
  40.          cout<<temp->element<<" ";  
  41.          temp = temp->pNext;  
  42.      }  
  43.      cout<<endl;  
  44.  }  
  45.  //函数功能：反转单链表  
  46.  Node* ReverseList(Node* head)  
  47.  {  
  48.     if((head == NULL) || (head->pNext == NULL)) //0个或1个结点  
  49.         return head;  
  50.       
  51.     Node* p = NULL;  
  52.     Node* tempHead = head;  
  53.     while (tempHead->pNext != NULL)  
  54.     {  
  55.         p = tempHead->pNext;  
  56.         tempHead->pNext = p->pNext;  
  57.         p->pNext = head;  
  58.         head = p;  
  59.     }  
  60.     return head;  
  61.  }  
  62. int main()  
  63. {  
  64.     int arr[10];  
  65.     for(int i=0; i<10; i++)  
  66.         arr[i] = i + 1;  
  67.     Node *head = BuildList(arr, 10);  
  68.     cout<<"反转前："<<endl;  
  69.     PrintList(head);  
  70.     cout<<"反转前："<<endl;  
  71.     head = ReverseList(head);  
  72.     PrintList(head);  
  73. }  

 

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

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <cassert>  
  3. using namespace std;  
  4. int Myatoi(const char *pstr)  
  5. {  
  6.     assert(pstr != NULL); //判断不为空  
  7.       
  8.     const char *temp = pstr;  
  9.     while (*temp == ' ') // 去除开头的空字符  
  10.         temp++;  
  11.     int result = 0;  
  12.     int flag = 1; // 正负值标志位  
  13.     if(*temp == '-') //若为负数  
  14.     {  
  15.         flag = -1;  
  16.         temp++;  
  17.     }  
  18.     while (*temp != '/0')  
  19.     {  
  20.         result = result * 10 + (*temp - '0');  
  21.         temp++;  
  22.     }  
  23.     return result * flag;  
  24. }  
  25. int main()  
  26. {  
  27.     const char* str1 = "1234";  
  28.     const char* str2 = "-567";  
  29.     const char* str3 = "  455";  
  30.     const char* str4 = "  -45677";  
  31.     cout<<Myatoi(str1)<<endl;  
  32.     cout<<Myatoi(str2)<<endl;  
  33.     cout<<Myatoi(str3)<<endl;  
  34.     cout<<Myatoi(str4)<<endl;  
  35. }  

 

9、编程实现两个正整数的除法
编程实现两个正整数的除法，当然不能用除法操作符。
// return x/y.
int div(const int x, const int y) 
{
  ....
}

[cpp] view plaincopy
  1. #include <iostream>  
  2. using namespace std;  
  3. /************************************************************************/  
  4. /* 函数功能：编程实现两个正整数的除法，当然不能用除法操作符             ×/ 
  5. /************************************************************************/  
  6. int Mydiv(const int x, const int y)   
  7. {  
  8.     int result = 0;  
  9.     int temp = x;  
  10.     while (temp >= y)  
  11.     {  
  12.         result++;  
  13.         temp = temp - y;  
  14.     }  
  15.     return result;  
  16. }  
  17. int main()  
  18. {  
  19.     cout<<Mydiv(20, 4)<<endl;  
  20.     cout<<Mydiv(20, 7)<<endl;  
  21. }  

 

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

[cpp] view plaincopy
  1. #include <iostream>  
  2. using namespace std;  
  3. /************************************************************************/  
  4. /* 函数功能：在排序数组中，找出给定数字的出现次数             
  5.    比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。 
  6.    陷阱：一个看到题，首先想到的方法是进行遍历统计，这样时间复杂度为O(N), 
  7.    但是题目明确说明是“排序数组”，所以使用二分查找的方法分别找出给定数字 
  8.    的开始和结束位置，最坏情况下时间复杂度为O(logn)。×/ 
  9. /************************************************************************/  
  10. //函数功能：返回最后一个等于x的位置  
  11. int getUpper(int arr[], int length, int x)  
  12. {  
  13.     int low = 0;  
  14.     int high = length - 1;  
  15.     int mid = 0;  
  16.     while (low <= high)  
  17.     {  
  18.          mid = (low + high) / 2;  
  19.         if(arr[mid] <= x) //向后查找  
  20.             low = mid + 1;  
  21.         else  
  22.             high = mid - 1;  
  23.     }  
  24.     return high;  
  25. }  
  26. //函数功能：返回第一个等于x的位置  
  27. int getLower(int arr[], int length, int x)  
  28. {  
  29.     int low = 0;  
  30.     int high = length - 1;  
  31.     int mid = 0;  
  32.     while (low <= high)  
  33.     {  
  34.         mid = (low + high) / 2;  
  35.         if(arr[mid] >= x) //向前查找  
  36.             high = mid - 1;   
  37.         else  
  38.             low = mid + 1;  
  39.     }  
  40.     return low;  
  41. }  
  42. //函数功能：返回x的次数  
  43. int GetTimes(int arr[], int length, int x)  
  44. {  
  45.     int low = getLower(arr, length,  x);  
  46.     int high = getUpper(arr, length, x);  
  47.     return (high - low + 1);  
  48. }  
  49. int main()  
  50. {  
  51.     int arr[] = {1, 2, 2, 2, 3};  
  52.     cout<<GetTimes(arr, sizeof(arr)/sizeof(arr[0]), 2)<<endl;;  
  53. }  

 

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

不会！

12、一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。

[cpp] view plaincopy
  1. /************************************************************************/  
  2. /* 算法思想： 
  3.     1、找到非零最大值a，找到非零最小值b O（1） 
  4.     2，计算s=a-b O（1） 
  5.     3, s>4 则不连续相邻， s<=4 连续相邻 O（1） 
  6.     代价为O（1）                                                        */  
  7. /************************************************************************/  

 

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

[cpp] view plaincopy
  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. #include <vector>  
  4. #include <deque>  
  5. #include <iterator>  
  6. using namespace std;  
  7. struct TNode  
  8. {  
  9.     int element;  
  10.     TNode* left;  
  11.     TNode* right;  
  12.     TNode(int ele = 0, TNode* l = NULL, TNode* t= NULL)  
  13.         :element(ele), left(l), right(t){}  
  14. };  
  15. /************************************************************************/  
  16. /*函数功能：将一个有序整数数组放到二叉树中                              */  
  17. /************************************************************************/  
  18. TNode* ConvertArrayToBinaryTree(int arr[], int current, int legth)  
  19. {  
  20.     TNode *root = NULL;  
  21.     if (current < legth)  
  22.     {  
  23.         root = new TNode(arr[current]);  
  24.         if(2*current + 1 < legth)  
  25.             root->left = ConvertArrayToBinaryTree(arr, 2*current + 1, legth);  
  26.         if(2*current + 2 < legth)  
  27.             root->right = ConvertArrayToBinaryTree(arr, 2*current + 2, legth);  
  28.     }  
  29.     return root;  
  30. }  
  31. /************************************************************************/  
  32. /*函数功能：输出根节点到给定节点pNode的路径                             */  
  33. /************************************************************************/  
  34. void PrintPath(TNode* root, vector<int> vec, TNode *pNode)  
  35. {  
  36.     if(root == NULL)  
  37.         return;  
  38.     TNode* temp = root;  
  39.     vec.push_back(temp->element);  
  40.     if(temp == pNode)  
  41.     {  
  42.         for(size_t i = 0; i < vec.size(); ++i)  
  43.             cout<<vec.at(i)<<" ";  
  44.         cout<<endl;  
  45.         return;  
  46.     }  
  47.     else  
  48.     {  
  49.         PrintPath(root->left, vec, pNode);  
  50.         PrintPath(root->right, vec, pNode);  
  51.     }  
  52. }  
  53. /************************************************************************/  
  54. /*函数功能：获取根节点到给定节点pNode的路径                             */  
  55. /************************************************************************/  
  56. void GetPath(TNode* root, vector<int> vec, TNode *pNode, vector<int>& path)  
  57. {  
  58.     if(root == NULL)  
  59.         return;  
  60.     TNode* temp = root;  
  61.     vec.push_back(temp->element);  
  62.     if(temp == pNode)  
  63.     {  
  64.         for (size_t i = 0; i < vec.size(); ++i)  
  65.             path.push_back(vec.at(i));  
  66.         return;  
  67.     }  
  68.     else  
  69.     {  
  70.         GetPath(root->left, vec, pNode, path);  
  71.         GetPath(root->right, vec, pNode, path);  
  72.     }  
  73. }  
  74. /************************************************************************/  
  75. /* 函数功能：出二叉树上任意两个结点的最近共同父结点                     */  
  76. /************************************************************************/  
  77. int GetCommonParentNode(TNode* root, TNode *node1, TNode* node2)  
  78. {  
  79.     vector<int> path1, path2, path;  
  80.     GetPath(root, path, node1, path1);  
  81.     GetPath(root, path, node2, path2);  
  82.     //找第一个不相同的节点  
  83.     size_t index1 = 0;  
  84.     size_t index2 = 0;  
  85.     while ((index2 < path2.size()) && (index1 < path1.size()))  
  86.     {  
  87.         if(path1.at(index1) != path2.at(index2))  
  88.             break;  
  89.         index2++;  
  90.         index1++;  
  91.     }  
  92.     return path1[index1 - 1];  
  93. }  
  94. int main()  
  95. {  
  96.     int arr[10];  
  97.     for (int i=0; i<10; i++)  
  98.         arr[i] = i+1;  
  99.     TNode *root = ConvertArrayToBinaryTree(arr, 0, sizeof(arr)/sizeof(arr[0]));  
  100.       
  101.     TNode *pNode = root->left->left->right;  
  102.     vector<int> vec;  
  103.     PrintPath(root, vec, pNode);  
  104.     TNode *node1 = root->left->left->left;  
  105.     TNode *node2 = root->left->right;  
  106.     int res = GetCommonParentNode(root, node1, node2);  
  107.     cout<<res<<endl;  
  108. }  

 

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

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

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <cstdlib>  
  3. using namespace std;  
  4. /* 
  5. 先排序，复杂度O（nlgn），然后用两个指示器（front和back）分别指向第一个和最后一个元素， 
  6. 如果A[front]+A[back]>N+1，则back--；  
  7. 如果A[front]+A[back]=N+1，则计数器加1，back--，同时front++；  
  8. 如果A[front]+A[back] <N+1，则front++；  
  9. 重复上述步骤，O（n）时间找到所有数对，总体复杂度为O（nlgn） 
  10. */  
  11. //比较函数  
  12. int cmp(const void *a, const void *b)    
  13. {    
  14.     return *(int *)a - *(int *)b;    
  15. }  
  16. int GetCount(int arr[], int length)  
  17. {  
  18.     qsort(arr, length, sizeof(int), cmp);  
  19.     int count = 0;  
  20.     int low = 0;  
  21.     int high = length - 1;  
  22.     int N = arr[high];  
  23.     while(low <= high)  
  24.     {  
  25.         if(arr[low] + arr[high] < N+1)  
  26.             low++;  
  27.         else if (arr[low] + arr[high] > N+1)  
  28.             high--;  
  29.         else  
  30.         {  
  31.             count++;  
  32.             cout<<arr[low]<<" "<<arr[high]<<endl;  
  33.             low++;  
  34.             high--;  
  35.         }  
  36.     }  
  37.     return count;  
  38. }  
  39. int main()  
  40. {  
  41.     int arr[] = {4, 5, 7, 8, 9, 1, 10, 13, 16};  
  42.     int length = sizeof(arr) / sizeof(arr[0]);  
  43.     int num = GetCount(arr, length);  
  44.     cout<<"个数为: "<<num<<endl;  
  45. }  

 

谷歌八道面试题

16、正整数序列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)、设计测试数据来验证函数程序在各种输入下的正确性。

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <iterator>  
  3. #include <cassert>  
  4. using namespace std;  
  5. void generate(int a, int b, int N, int * Q)  
  6. {  
  7.     int num = 0; //计数  
  8.     int index = 1;   
  9.     while (num < N)  
  10.     {  
  11.         if ((index%a == 0) || ( index%b == 0)) //若index满足条件。放到数组Q  
  12.         {  
  13.             Q[num++] = index;  
  14.         }  
  15.         index++;  
  16.     }  
  17. }  
  18. int main()  
  19. {  
  20.     int N = 6;  
  21.     int *arr = new int[N];  
  22.     generate(3, 5, 6, arr);  
  23.       
  24.     copy(arr, arr+N, ostream_iterator<int>(cout, " "));  
  25.     cout<<endl;  
  26. }  

 

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

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <iterator>  
  3. #include <cassert>  
  4. using namespace std;  
  5. void proc(char *str)  
  6. {  
  7.     assert(str != NULL);  
  8.     int length = strlen(str);  
  9.     char *begin = str;  
  10.     char *end = str + length - 1;  
  11.     while(begin < end)  
  12.     {  
  13.         while (islower(*begin))  
  14.             begin++;  
  15.         while (isupper(*end))  
  16.             end--;  
  17.         char temp = *begin;  
  18.         *begin = *end;  
  19.         *end = temp;  
  20.         begin++;  
  21.         end--;  
  22.     }  
  23. }  
  24. int main()  
  25. {  
  26.     char str[] = "aDsfGGrr";  
  27.     proc(str);  
  28.     cout<<str<<endl;  
  29. }  

 

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

      定义长度为1000的数组。
　　对于数据流中的前1000个关键字，显然都要放到数组中。
　　对于数据流中的的第n(n>1000)个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键       字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。
　　对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。

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

假设待判断的数字是 N。

方法1：
遍历从1到N的数字，求取平方并和N进行比较。
如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。
复杂度为O(n^0.5)。

方法2：
使用二分查找法，对1到N之间的数字进行判断。
复杂度为O(log n)。

方法3：
由于
(n+1)^2 
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到这些项构成了等差数列（每项之间相差2）。
所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的关系。
如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。
复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。

21、1024! 末尾有多少个0？

末尾0的个数取决于乘法中因子2和5的个数。显然乘法中因子2的个数大于5的个数，所以我们只需统计因子5的个数。
是5的倍数的数有： 1024 / 5 = 204个
是25的倍数的数有：1024 / 25 = 40个
是125的倍数的数有：1024 / 125 = 8个
是625的倍数的数有：1024 / 625 = 1个
所以1024! 中总共有204+40+8+1=253个因子5。
也就是说1024! 末尾有253个0。 

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

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

这个问题,应该逼近法
数组 数组biaozhi[0..9] biaozhi[i]=true 则表示i包含在集合中,0<=i<=9;
从整数k的高位往底位判断
  设k当前位的数值为i,
  if biaozhi[i]=true
  {
  进行下一位判断;
  }
  else //biaozhi[i]=false
  {
  当集合中有比i大的值记为m,则 把k的当前位用m代替,从k位下一位往个位用集合中最小值填充
  当集合中没有比i大的值,则从k的上1位回溯
  }  

[cpp] view plaincopy
  1. // Google.cpp : Defines the entry point for the console application.  
  2. //  
  3. #include "stdafx.h"  
  4. #include <iostream>  
  5. #include <set>  
  6. #include <stack>  
  7. #include <list>  
  8. using namespace std;  
  9. int GetMinK(set<int> inputSet, int K)  
  10. {  
  11.     //求整数K的位数，并将每一位存储到stack中  
  12.     int n = 0;  
  13.     stack<int> s;  
  14.     while (K != 0)  
  15.     {  
  16.         n++;  
  17.         s.push(K%10);  
  18.         K /= 10;  
  19.     }  
  20.     list<int> result;  
  21.     for (int i=0; i<n; i++)  
  22.     {  
  23.         while (!s.empty() && inputSet.find(s.top()) != inputSet.end()) //集合中存在整数第i位(高位为第0位)的元素值  
  24.         {  
  25.             result.push_back(s.top());  
  26.             s.pop();  
  27.         }  
  28.         if (s.empty() == true) //若各位都在集合inputSet中  
  29.         {  
  30.             set<int>::iterator iter;  
  31.             while (!result.empty())  
  32.             {  
  33.                 iter = inputSet.upper_bound(result.back());  
  34.                 while (!result.empty() && iter == inputSet.end())  
  35.                 {  
  36.                     result.pop_back();  
  37.                     iter = inputSet.upper_bound(result.back());  
  38.                 }  
  39.                 if(!result.empty())  
  40.                 {  
  41.                     result.pop_back();  
  42.                     result.push_back(*iter);  
  43.                     for (int j= result.size(); j<n; j++)  
  44.                         result.push_back(*inputSet.begin());  
  45.                     break;  
  46.                 }  
  47.                 if(result.empty())  
  48.                 {  
  49.                     iter = inputSet.upper_bound(0);  
  50.                     result.push_back(*iter);  
  51.                     for(int j=0; j<n; j++)  
  52.                         result.push_back(*inputSet.begin());  
  53.                     break;  
  54.                 }  
  55.             }  
  56.         }  
  57.         else  
  58.         {  
  59.             if (inputSet.find(s.top()) == inputSet.end()) //集合中不存在整数第i位(高位为第0位)的元素值  
  60.             {  
  61.                 set<int>::iterator iter = inputSet.lower_bound(s.top());  
  62.                 if (iter != inputSet.end()) //集合中存在比整数第i位(高位为第0位)大的元素值  
  63.                 {  
  64.                     result.push_back(*iter);  
  65.                     for (int j=i+1; j<n; j++)  
  66.                         result.push_back(*inputSet.begin());  
  67.                     break;  
  68.                 }  
  69.                 if (iter == inputSet.end()) //集合中不存在比整数第i位(高位为第0位)大的元素值  
  70.                 {  
  71.                     if(result.empty() == true) //若第一位不存在集合中  
  72.                     {  
  73.                         iter = inputSet.upper_bound(0);  
  74.                         result.push_back(*iter);  
  75.                         for(int j=0; j<n; j++)  
  76.                             result.push_back(*inputSet.begin());  
  77.                         break;  
  78.                     }  
  79.                     else  
  80.                     {  
  81.                         while(!result.empty()) //进行回退  
  82.                         {  
  83.                             iter  = inputSet.upper_bound(result.back());  
  84.                             if(iter == inputSet.end())  
  85.                             {  
  86.                                 result.pop_back(); i--;  
  87.                             }  
  88.                             else  
  89.                             {  
  90.                                 result.pop_back();  
  91.                                 result.push_back(*iter);  
  92.                                 for (int j=i+1; j<n; j++)  
  93.                                     result.push_back(*inputSet.begin());  
  94.                                 break;  
  95.                             }  
  96.                         }  
  97.                         break;  
  98.                     }  
  99.                 }  
  100.             }  
  101.         }  
  102.     }  
  103.     if (s.empty() == true)  
  104.     {  
  105.     }  
  106.     int res = 0;  
  107.     while (!result.empty())  
  108.     {  
  109.         res = res * 10 + result.front();  
  110.         result.pop_front();  
  111.     }  
  112.     return res;  
  113. }  
  114. int _tmain(int argc, _TCHAR* argv[])  
  115. {  
  116.     set<int> s;  
  117.     s.insert(1);  
  118.     s.insert(0);  
  119.     int res = GetMinK(s, 21);  
  120.     cout<<res<<endl;  
  121.     return 0;  
  122. }  

 

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

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

解析：可以采用鬼魂算法，鬼魂的意思就是“传递能量”，“穿透”。

首先判断最靠近中间点的蚂蚁，用程序很好判断，就是11厘米处的蚂蚁，其实这个蚂蚁，最快的时间就是最小时间。

其次判断最靠外面的蚂蚁，用程序很好判断，就是3厘米处的蚂蚁，其实这个蚂蚁，最慢的时间就是最大时间。

其他蚂蚁无视就可以了。

答案：最大时间是27-3=24，最小时间是11-0=11。

雅虎三道面试题

34、编程实现：把十进制数(long型)分别以二进制和十六进制形式输出，不能使用printf系列

[cpp] view plaincopy
  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. using namespace std;  
  4. /************************************************************************/  
  5. /* 函数功能：把十进制数(long型)分别以二进制                             */  
  6. /************************************************************************/  
  7. void LongTo2(long n)  
  8. {  
  9.     if(0 == n)  
  10.         return;  
  11.     else  
  12.     {  
  13.         LongTo2(n/2);  
  14.         cout<<n%2;  
  15.     }  
  16. }  
  17. /************************************************************************/  
  18. /* 函数功能：把十进制数(long型)分别以16进制                             */  
  19. /************************************************************************/  
  20. const char arr[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',  
  21.                       'A', 'B', 'C', 'D', 'E', 'F'};  
  22. void LongTo16(long n)  
  23. {  
  24.     if(0 == n)  
  25.         return;  
  26.     else  
  27.     {  
  28.         LongTo16(n/16);  
  29.         cout<<arr[n%16];  
  30.     }  
  31. }  
  32. int main()  
  33. {  
  34.     LongTo2(56);  
  35.     cout<<endl;  
  36.     LongTo16(256);  
  37.     cout<<endl;  
  38. }  
 

35、编程实现：找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为"cad"

[cpp] view plaincopy
  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. using namespace std;  
  4. /************************************************************************/  
  5. /* 函数功能：找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大 
  6.              子串为"cad"*/  
  7. /************************************************************************/  
  8. void GetMaxCommonSubString(const char *str1, const char *str2, char* &subString)  
  9. {  
  10.     int length1 = strlen(str1);  
  11.     int length2 = strlen(str2);  
  12.     int max = 0; //存储最大值  
  13.     int start = 0;//最大公共字串在str1中开始的位置  
  14.     for (int i=0; i<length1; i++)  
  15.     {  
  16.         for (int j=0; j<length2; j++)  
  17.         {  
  18.             int temp1 = i; //每次查找的开始位置  
  19.             int temp2 = j;  
  20.             int number = 0; //统计个数  
  21.             while ((str1[temp1] == str2[temp2]) && (temp2 < length2) && (temp1 < length1)) //开始找公共字串  
  22.             {  
  23.                 number++;  
  24.                 temp1++;  
  25.                 temp2++;  
  26.             }  
  27.             if (number > max) //判断是否是最大的  
  28.             {  
  29.                 max = number;  
  30.                 start = i;  
  31.             }  
  32.         }  
  33.     }  
  34.     strncpy(subString, str1 + start, max); //拷贝到subString中  
  35. }  
  36. int main()  
  37. {  
  38.     const char* str1 = "abccade";  
  39.     const char* str2 = "dgcadde";  
  40.     int length = (strlen(str1) <= strlen(str2) ? strlen(str1) : strlen(str2));  
  41.     char *str = new char[length];  
  42.     memset(str, '/0', length+1);  
  43.     GetMaxCommonSubString(str1, str2, str);  
  44.     cout<<str<<endl;  
  45. }  
 

38、顺时针打印矩阵
题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
例如：如果输入如下矩阵：

1              2              3              4
5              6              7              8
9              10             11             12
13             14             15             16
则依次打印出数字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。

分析：包括Autodesk、EMC在内的多家公司在面试或者笔试里采用过这道题。

[cpp] view plaincopy
  1. #include <iostream>  
  2. using namespace std;  
  3. /************************************************************************/  
  4. /*函数功能：顺时针打印矩阵，m表示矩阵的行，n表示矩阵的列                */  
  5. /************************************************************************/  
  6. void PrintMatrix(int **matrix, int m, int n)  
  7. {  
  8.     int numbers = m * n;  
  9.     int num = 0;  
  10.     for (int i=0; i<=m/2; i++)  
  11.     {  
  12.         for (int j=i; j<n-i; j++, num++)  
  13.             printf("%d ", matrix[i][j]); //打印上边的行  
  14.               
  15.         for (int k=i+1; k<m-i-1; k++, num++)  
  16.         {  
  17.             if(num >= numbers)  
  18.                 break;  
  19.             printf("%d ", matrix[k][n-i-1]); //打印右边的列  
  20.         }  
  21.         for (int j=n-i-1; j>=i; j--, num++)  
  22.         {  
  23.             if(num >= numbers)  
  24.                 break;  
  25.             printf("%d ", matrix[m-i-1][j]); //打印下边的行  
  26.         }  
  27.         for(int k= m-i-2; k>i; k--, num++)  
  28.         {  
  29.             if(num > numbers)  
  30.                 break;  
  31.             printf("%d ", matrix[k][i]); //打印左边的行  
  32.         }  
  33.     }  
  34.     printf("/n");  
  35. }  
  36. int main()  
  37. {  
  38.     int **matrix;  
  39.     const int M = 5;   
  40.     const int N = 4;  
  41.     matrix = new int*[M];  
  42.     for (int i=0; i<M; i++)  
  43.         matrix[i] = new int[N];  
  44.     int k = 1;  
  45.     for(int i=0; i<M; i++)  
  46.         for(int j=0; j<N; j++)  
  47.             matrix[i][j] = k++;  
  48.       
  49.     PrintMatrix(matrix, M, N);  
  50. }  
 

39、对称子字符串的最大长度
题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <cassert>  
  3. using namespace std;  
  4. /************************************************************************/  
  5. /* 函数功能：判断low和high之间的字符串是否是对称的                      */  
  6. /************************************************************************/  
  7. bool isDuiChen(const char* low, const char* high)  
  8. {  
  9.     while (low < high)  
  10.     {  
  11.         if (*low == *high)  
  12.         {  
  13.             low++;  
  14.             high--;  
  15.         }  
  16.         else  
  17.             return false;  
  18.     }  
  19.     return true;  
  20. }  
  21. /************************************************************************/  
  22. /* 函数功能：求字符串str中对称字符串的最大长度,result存放该字串         */  
  23. /************************************************************************/  
  24. int getMaxLength(const char* str, char* result)  
  25. {  
  26.     assert(str != NULL);  
  27.     int len = strlen(str);  
  28.     int max = 0;  
  29.     int start = 0;  
  30.     for (int i=0; i<len-1; i++)  
  31.     {  
  32.         for (int j= i+1; j<len; j++)  
  33.         {  
  34.             if (isDuiChen(str+i, str+j))  
  35.             {  
  36.                 if((j - i + 1) > max)  
  37.                 {  
  38.                     max = j - i + 1;  
  39.                     start = i;  
  40.                 }  
  41.             }  
  42.         }  
  43.     }  
  44.     strncpy(result, str + start, max);  
  45.     return max;  
  46. }  
  47. int main()  
  48. {  
  49.     const char *str = "googleyanggnay";  
  50.     int len = strlen(str);  
  51.     char *result = new char[len + 1];  
  52.     memset(result, '/0', len + 1);  
  53.     int max = getMaxLength(str, result);  
  54.     printf("最大的对称字串为：%s, 长度为: %d/n", result, max);  
  55. }  

 

40、用1、2、2、3、4、5这六个数字，写一个main函数，打印出所有不同的排列，
如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连.

[cpp] view plaincopy
  1. #include <iostream>  
  2. using namespace std;  
  3. char result[7] = {'/0'};  
  4. void PrintSpecialPaiLie(char *str, int curPos, int n)  
  5. {  
  6.     if (curPos == n)  
  7.     {  
  8.         if ((str[3] != '4') && (strstr(str, "35") == NULL)) //对输出进行过滤  
  9.             printf("%s/n", str);  
  10.     }  
  11.     else  
  12.     {  
  13.         for (int i = curPos; i<n; i++)  
  14.         {  
  15.             swap(str[0], str[i]);  
  16.             PrintSpecialPaiLie(str, curPos + 1, n);  
  17.             swap(str[0], str[i]);  
  18.         }  
  19.     }  
  20. }  
  21. int main()  
  22. {  
  23.     char str[] = "122345";  
  24.     int N = sizeof(str) / sizeof(char) - 1; //减1是因为str中含有字符'/0';  
  25.     PrintSpecialPaiLie(str, 0, N);  
  26. }  

 

48、找出数组中唯一的重复元素

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次．
每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，
能否设计一个算法实现？

[cpp] view plaincopy
  1. #include <iostream>  
  2. using namespace std;  
  3. /* 
  4.     算法思想：统计数组的全部元素之和sum，然后根据等差数列求出1到upperBound这些 
  5.     数字的和n，然后重复的数字为sum-n。  
  6. */  
  7. int findDuplicateElement(int arr[], int upperBound)  
  8. {  
  9.     int sum = 0;  
  10.     for(int i = 0; i < upperBound + 1 ; i++)  
  11.         sum += arr[i];  
  12.     return sum - (1 + upperBound) * upperBound / 2;  
  13. }  
  14. int main()  
  15. {  
  16.     const int NUMBERS = 1001;  
  17.     int arr[NUMBERS];  
  18.       
  19.     for(int i = 0; i < NUMBERS; ++i)  
  20.         arr[i] = i + 1;  
  21.           
  22.     arr[NUMBERS - 1] = 520;  //设定重复元素   
  23.       
  24.     int result = findDuplicateElement(arr, NUMBERS - 1);  
  25.     cout<<"重复元素为: "<<result<<endl;  
  26.       
  27. }  

 

50、一道SPSS笔试题求解

题目：输入四个点的坐标，求证四个点是不是一个矩形
关键点：
1.相邻两边斜率之积等于-1，
2.矩形边与坐标系平行的情况下，斜率无穷大不能用积判断。
3.输入四点可能不按顺序，需要对四点排序。

[cpp] view plaincopy
  1. // ww.cpp : Defines the entry point for the console application.  
  2. //  
  3. #include "stdafx.h"  
  4. #include <iostream>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. //向量的类  
  8. struct Vector  
  9. {  
  10.     int x;   
  11.     int y;  
  12.     Vector(){}  
  13.     Vector(int _x, int _y)  
  14.     {  
  15.         x = _x; y = _y;  
  16.     }  
  17.     bool operator* (const Vector& other) //定义两个向量相乘  
  18.     {  
  19.         if((x * other.x + y * other.y) == 0)  
  20.             return true;  
  21.         return false;  
  22.     }  
  23. };  
  24. //点的类  
  25. struct Point  
  26. {  
  27.     int x;  
  28.     int y;  
  29.     Point(){}  
  30.     Point(int _x, int _y)  
  31.     {  
  32.         x = _x; y = _y;  
  33.     }  
  34.     Vector operator- (const Point& other) //定义两个点相减  
  35.     {  
  36.         return Vector(other.x - x, other.y - y);  
  37.     }  
  38. };  
  39. bool cmp(const Point& lv, const Point& rv)  
  40. {  
  41.     return ((lv.x < rv.x) || (lv.x == rv.x && lv.y < rv.y));  
  42. }  
  43. //判断四个点是否构成矩形  
  44. bool IsRectangle(Point arr[4])  
  45. {  
  46.     sort(arr, arr + 4, cmp);  
  47.     Vector v01 = arr[1] - arr[0];  
  48.     Vector v03 = arr[2] - arr[0];  
  49.     if(v03 * v01 == false)  
  50.         return false;  
  51.     Vector v21 = arr[0] - arr[1];  
  52.     Vector v23 = arr[3] - arr[1];  
  53.     if(v21 * v23 == false)  
  54.         return false;  
  55.     Vector v32 = arr[0] - arr[2];  
  56.     Vector v34 = arr[3] - arr[2];  
  57.     if(v32 * v34 == false)  
  58.         return false;  
  59.     Vector v41 = arr[1] - arr[3];  
  60.     Vector v43 = arr[2] - arr[3];  
  61.     if (v41 * v43 == false)  
  62.         return false;  
  63.       
  64.     return true;  
  65. }  
  66. int _tmain(int argc, _TCHAR* argv[])  
  67. {  
  68.     Point arr[4] = {Point(1, 0), Point(0, 6), Point(-1, 0), Point(0, -1)};  
  69.     if (IsRectangle(arr))  
  70.         cout<<"是矩形"<<endl;  
  71.     else  
  72.         cout<<"不是矩形"<<endl;  
  73.     return 0;  
  74. }  

 

取值为【1，n-1】含n个元素的整数数组至少存在一个重复数，O（n）时间内找出其中任意一个重复数

[cpp] view plaincopy
  1. // ww.cpp : Defines the entry point for the console application.  
  2. //  
  3. #include "stdafx.h"  
  4. #include <iostream>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. /* 
  8. 取值为【1，n-1】含n个元素的整数数组至少存在一个重复数，O（n）时间内找出其中任意一个重复数 
  9. */  
  10. /* 
  11. 思路分析： 
  12. 1、如果数组中有且仅有一个重复数，可以简单的通过S(A)=(n-1)*n/2得到重复数，其中S(A)表示对数组A求和 
  13. 2、仿链表中找环的思路解决至少含一个重复数的问题 
  14. */  
  15. int GetRepeatNumber(int arr[], int n)  
  16. {  
  17.     int x = 0, y = 0;  
  18.     do   
  19.     {  
  20.         x = arr[arr[x]];  
  21.         y = arr[y];  
  22.     } while (x != y);  
  23.     return arr[x];  
  24. }  
  25. int main()  
  26. {  
  27.     int arr[10] = {1, 4, 3, 5, 4, 5, 5, 4, 8, 9};  
  28.     cout<<"重复的数字为："<<GetRepeatNumber(arr, 10)<<endl;  
  29. }  

 

 

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/mfryf/p/2616707.html