全新整理：微软、Google等公司的面试题及解答、第161-170题

旧城等待， 2021-12-01 23:40 685阅读 0赞

全新整理：微软、Google等公司非常好的面试题及解答、第161-170题

整理：July。  
时间：二零一一年四月十日。  
微博：[**http://weibo.com/julyweibo**][http_weibo.com_julyweibo]。  
出处：[**http://blog.csdn.net/v\_JULY\_v**][http_blog.csdn.net_v_JULY_v]。  
\-------------------------------

**引言**  
    此微软100题V0.2版的前60题，请见这：[微软、谷歌、百度等公司经典面试100题\[第1-60题\]][100_1-60]。关于本人整理[***微软100题***][100]的一切详情，请参见这：[**横空出世，席卷Csdn \[评微软等数据结构+算法面试100题\]**][Csdn _100]。

**声明**  
    1、下面的题目来不及一一细看，答案大部是摘自网友，且个人认为比较好一点的思路，对这些思路和答案本人未经细细验证，仅保留意见。  
    2、为尊重作者劳动成果，凡是引用了网友提供的面试题、思路，或答案，都一一注明了网友的昵称。若对以下任何一题的思路，不是很懂的，欢迎留言或评论中提出，我可再做详细阐述。  
    3、以下的每一题，都是自个平时一一搜集整理的，转载请务必注明出处。任何人，有任何问题，欢迎不吝指正。谢谢。

**微软、Google等公司一些非常好的面试题、第61-70题  
61**、腾讯现场招聘问题  
liuchen1206  
今天参加了腾讯的现场招聘会，碰到这个一个题目：  
  在一篇英文文章中查找指定的人名，人名使用二十六个英文字母（可以是大写或小写）、空格以及两个通配符组成（\*、?），通配符“\*”表示零个或多个任意字母，通配符“?”表示一个任意字母。  
如：“J\* Smi??” 可以匹配“John Smith” .

请用C语言实现如下函数：  
void scan(const char\* pszText, const char\* pszName);  
注：pszText为整个文章字符，pszName为要求匹配的英文名。  
请完成些函数实现输出所有匹配的英文名，除了printf外，不能用第三方的库函数等。

**代码一（此段代码已经多个网友指出，bug不少，但暂没想到解决办法）：**

1.  **//copyright@ falcomavin && July  **
2.  **  **
3.  **//updated：  **
4.  **//多谢Yingmg网友指出，由于之前这代码是从编译器->记事本->本博客，辗转三次而来的，  **
5.  **//所以，之前的代码不符合缩进规范，  **
6.  **//特此再把它搬到编译器上，调整好缩进后，不再放到记事本上，而是直接从编译器上贴到这里来。  **
7.  **  **
8.  **//July，说明。2011.04.17。  **
9.  **\#include <iostream>  **
10. **using namespace std;  **
11. **  **
12. **int scan(const char\* text, const char\* pattern)  **
13. **\{  **
14. **    const char \*p = pattern;    // 记录初始位置，以便patten匹配一半失败可返回原位  **
15. **    if (\*pattern == 0) return 1;    // 匹配成功条件  **
16. **    if (\*text == 0) return 0;    // 匹配失败条件  **
17. **      **
18. **    if (\*pattern != '\*' && \*pattern != '?')  **
19. **    \{  **
20. **        if (\*text != \*pattern)    //如果匹配不成功    **
21. **            return scan(text+1, pattern);    //text++，寻找下一个匹配  **
22. **    \}  **
23. **      **
24. **    if (\*pattern == '?')  **
25. **    \{  **
26. **        if (!isalpha(\*text))    // 通配符'?'匹配失败  **
27. **        \{  **
28. **            pattern = p;    // 还原pattern初始位置  **
29. **            return scan(text+1, pattern);    //text++，寻找下一个匹配  **
30. **        \}  **
31. **        else                    // 通配符'?'匹配成功  **
32. **        \{  **
33. **            return scan(text+1, pattern + 1);  //双双后移，++  **
34. **        \}  **
35. **    \}  **
36. **    return scan(text, pattern+1);    // 能走到这里，一定是在匹配通配符'\*'了  **
37. **\}  **
38. **  **
39. **int main()  **
40. **\{  **
41. **    char \*i, \*j;  **
42. **    i = new char\[100\];  **
43. **    j = new char\[100\];  **
44. **    cin>>i>>j;  **
45. **    cout<<scan(i,j);  **
46. **    return 0;  **
47. **\}  **

**代码二：**

1.  **//qq120848369：  **
2.  **\#include <iostream>  **
3.  **using namespace std;  **
4.  **const char \*pEnd=NULL;  **
5.  **  **
6.  **bool match(const char \*pszText,const char \*pszName)  **
7.  **\{  **
8.  **    if(\*pszName == '/0')    // 匹配完成  **
9.  **    \{  **
10. **        pEnd=pszText;  **
11. **        return true;  **
12. **    \}  **
13. **   **
14. **    if(\*pszText == '/0')    //    未匹配完成  **
15. **    \{  **
16. **        if(\*pszName == '\*')  **
17. **        \{  **
18. **            pEnd=pszText;  **
19. **            return true;  **
20. **        \}  **
21. **    **
22. **        return false;  **
23. **    \}  **
24. **   **
25. **    if(\*pszName!= '\*' && \*pszName!='?')  **
26. **    \{  **
27. **        if(\*pszText == \*pszName)  **
28. **        \{  **
29. **            return match(pszText+1,pszName+1);  **
30. **        \}  **
31. **    **
32. **        return false;  **
33. **    \}  **
34. **    else  **
35. **    \{  **
36. **        if(\*pszName == '\*')  **
37. **        \{  **
38. **            return match(pszText,pszName+1)||match(pszText+1,pszName);   **
39. **             //匹配0个,或者继续\*匹配下去  **
40. **        \}  **
41. **        else  **
42. **        \{  **
43. **            return match(pszText+1,pszName+1);  **
44. **        \}  **
45. **    \}  **
46. **\}  **
47. **  **
48. **void scan(const char \*pszText, const char \*pszName)  **
49. **\{  **
50. **    while(\*pszText!='/0')  **
51. **    \{  **
52. **        if(match(pszText,pszName))  **
53. **        \{  **
54. **            while(pszText!=pEnd)  **
55. **            \{  **
56. **                cout<<\*pszText++;  **
57. **            \}  **
58. **     **
59. **            cout<<endl;  **
60. **        \}    **
61. **        return;  **
62. **    \}  **
63. **\}  **
64. **  **
65. **int main()  **
66. **\{  **
67. **    char pszText\[100\],pszName\[100\];  **
68. **   **
69. **    fgets(pszText,100,stdin);  **
70. **    fgets(pszName,100,stdin);  **
71. **    scan(pszText,pszName);  **
72. **   **
73. **    return 0;  **
74. **\}  **

**wangxugangzy05：**  
这个是kmp子串搜索（匹配），稍加改造，如 abcabd\*?abe\*\*??de这个窜，我们可以分成abcabd,?,abe,?,?,并按顺序先匹配abcabd，当匹配后，将匹配的文章中地址及匹配的是何子串放到栈里记录下来，这样，每次匹配都入栈保存当前子串匹配信息，当一次完整的全部子串都匹配完后，就输出一个匹配结果，然后回溯一下，开始对栈顶的子串的进行文中下一个起始位置的匹配。

**62**、微软三道面试题  
yeardoublehua  
1. 给一个有N个整数的数组S..和另一个整数X，判断S里有没有2个数的和为X，  
请设计成O（n\*log2(n)）的算法。  
2. 有2个数组..里面有N个整数。  
设计一个算法O(n log2(n))，看是否两个数组里存在一个同样的数。  
3. 让你排序N个比N^7小的数，要求的算法是O(n)（给了提示..说往N进制那方面想）

**qq120848369：  
1,快排,头尾夹逼.**

1.  **\#include <iostream>  **
2.  **\#include <algorithm>  **
3.  **\#include <utility>  **
4.  **using namespace std;  **
5.  **typedef pair<int,int> Pair;  **
6.  **  **
7.  **Pair findSum(int \*s,int n,int x)  **
8.  **\{  **
9.  **    sort(s,s+n);   //引用了库函数  **
10. **  **
11. **    int \*begin=s;  **
12. **    int \*end=s+n-1;  **
13. **  **
14. **    while(begin<end)    //俩头夹逼，很经典的方法  **
15. **    \{  **
16. **        if(\*begin+\*end>x)  **
17. **        \{  **
18. **            --end;  **
19. **        \}  **
20. **        else if(\*begin+\*end<x)  **
21. **        \{  **
22. **            ++begin;  **
23. **        \}  **
24. **        else  **
25. **        \{  **
26. **            return Pair(\*begin,\*end);  **
27. **        \}  **
28. **    \}  **
29. **  **
30. **    return Pair(-1,-1);  **
31. **\}  **
32. **  **
33. **int main()  **
34. **\{    **
35. **    int arr\[100\]=  **
36. **    \{  **
37. **        3, -4, 7, 8, 12, -5, 0, 9  **
38. **    \};  **
39. **      **
40. **    int n=8,x;  **
41. **  **
42. **    while(cin>>x)  **
43. **    \{  **
44. **        Pair ret=findSum(arr,n,x);  **
45. **        cout<<ret.first<<","<<ret.second<<endl;  **
46. **    \}  **
47. **  **
48. **    return 0;  **
49. **\}  **

**2,快排,线性扫描**

1.  **\#include <iostream>  **
2.  **\#include <algorithm>  **
3.  **using namespace std;  **
4.  **  **
5.  **bool findSame(const int \*a,int len1,const int \*b,int len2,int \*result)  **
6.  **\{  **
7.  **    int i,j;  **
8.  **    i=j=0;  **
9.  **  **
10. **    while(i<len1 && j<len2)  **
11. **    \{  **
12. **        if(a\[i\]<b\[j\])  **
13. **        \{  **
14. **            ++i;  **
15. **        \}  **
16. **        else if(a\[i\]>b\[j\])  **
17. **        \{  **
18. **            ++j;  **
19. **        \}  **
20. **        else  **
21. **        \{  **
22. **            \*result=a\[i\];  **
23. **            return true;  **
24. **        \}  **
25. **    \}  **
26. **    return false;  **
27. **\}  **
28. **  **
29. **int main()  **
30. **\{  **
31. **    int a\[100\],b\[100\],len1,len2,result;  **
32. **    cin>>len1;  **
33. **  **
34. **    for(int i=0;i<len1;++i)  **
35. **    \{  **
36. **        cin>>a\[i\];  **
37. **    \}  **
38. **  **
39. **    cin>>len2;  **
40. **    for(int i=0;i<len2;++i)  **
41. **    \{  **
42. **        cin>>b\[i\];  **
43. **    \}  **
44. **  **
45. **    if( findSame(a,len1,b,len2,&result) )  **
46. **    \{  **
47. **        cout<<result<<endl;  **
48. **    \}  **
49. **    return 0;  **
50. **\}  **

**3,基数排序已经可以O(n)了**,准备10个vector<int>,从最低位数字开始,放入相应的桶里,然后再顺序取出来,然后再从次低位放入相应桶里,在顺序取出来.比如：N=5，分别是：4,10,7,123,33  
0 ：10  
1   
2   
3 ：123,33  
4 ：4  
5   
6   
7 ：7  
8   
9

顺次取出来：10,123,33,,4,7  
0 ：4,7  
1 ：10  
2 ：123  
3 ：33  
4   
5   
6   
7   
8   
9

依次取出来：4,7,10,123,33  
0 ：4,7，10，33  
1 ：123  
2   
3   
4   
5   
6   
7   
8   
9

依次取出来：4,7,10,33,123  
完毕。  
代码，如下：

1.  **\#include <iostream>  **
2.  **\#include <string>  **
3.  **\#include <queue>  **
4.  **\#include <vector>  **
5.  **  **
6.  **using namespace std;  **
7.  **  **
8.  **size\_t n;    //n个数  **
9.  **size\_t maxLen=0;    //最大的数字位数  **
10. **vector< queue<string> > vec(10);    //10个桶  **
11. **vector<string> result;  **
12. **  **
13. **void sort()  **
14. **\{  **
15. **    for(size\_t i=0;i<maxLen;++i)  **
16. **    \{  **
17. **        for(size\_t j=0;j<result.size();++j)  **
18. **        \{  **
19. **            if( i>=result\[j\].length() )  **
20. **            \{  **
21. **                vec\[0\].push(result\[j\]);  **
22. **            \}  **
23. **            else  **
24. **            \{  **
25. **                vec\[ result\[j\]\[result\[j\].length()-1-i\]-'0' \].push(result\[j\]);  **
26. **            \}  **
27. **        \}  **
28. **  **
29. **        result.clear();  **
30. **  **
31. **        for(size\_t k=0;k<vec.size();++k)  **
32. **        \{  **
33. **            while(!vec\[k\].empty())  **
34. **            \{  **
35. **                result.push\_back(vec\[k\].front());  **
36. **                vec\[k\].pop();  **
37. **            \}  **
38. **        \}  **
39. **    \}  **
40. **\}  **
41. **  **
42. **int main()  **
43. **\{  **
44. **    cin>>n;  **
45. **      **
46. **    string input;  **
47. **  **
48. **    for(size\_t i=0;i<n;++i)  **
49. **    \{  **
50. **        cin>>input;  **
51. **        result.push\_back(input);  **
52. **  **
53. **        if(maxLen == 0 || input.length()>maxLen)  **
54. **        \{  **
55. **            maxLen=input.length();  **
56. **        \}  **
57. **    \}  **
58. **  **
59. **    sort();  **
60. **  **
61. **    for(size\_t i=0;i<n;++i)  **
62. **    \{  **
63. **        cout<<result\[i\]<<"  ";  **
64. **    \}  **
65. **  **
66. **    cout<<endl;  **
67. **  **
68. **    return 0;  **
69. **\}  **

**xiaoboalex：**  
第一题，1. 给一个有N个整数的数组S..和另一个整数X，判断S里有没有2个数的和为X，  
请设计成O（n\*log2(n)）的算法。

如果限定最坏复杂度nlgn的话就不能用快排。  
可以用归并排序，然后Y=X-E，用两分搜索依次查找每一个Y是否存在，保证最坏复杂度为nlgn.

**63**、微软亚洲研究院  
hinyunsin  
假设有一颗二叉树，已知这棵树的节点上不均匀的分布了若干石头，石头数跟这棵二叉树的节点数相同，石头只可以在子节点和父节点之间进行搬运，每次只能搬运一颗石头。请问如何以最少的步骤将石头搬运均匀，使得每个节点上的石头上刚好为1。

个人，暂时还没看到清晰的，更好的思路，以下是网友mathe、casahama、Torey等人给的思路：  
**mathe：**  
我们对于任意一个节点，可以查看其本身和左子树，右子树的几个信息:  
i)本身上面石子数目  
ii)左子树中石子数目和节点数目的差值  
iii)右子树中石子数目和节点数目的差值  
iv)通过i),ii),iii)可以计算出除掉这三部份其余节点中石子和节点数目的差值。  
如果上面信息都已经计算出来，那么对于这个节点，我们就可以计算出同其关联三条边石子运送最小数目。比如，如果左子树石子数目和节点数目差值为a<0,那么表示比如通过这个节点通向左之数的边至少运送a个石子；反之如果a>0,那么表示必须通过这个节点通向左子树的边反向运送a个石子。同样可以计算出同父节点之间的最小运送数目。  
然后对所有节点，将这些数目（ii,iii,iv中)绝对值相加就可以得出下界。  
而证明这个下界可以达到也很简单。每次找出一个石子数目大于1的点，那么它至少有一条边需要向外运送，操作之即可。每次操作以后，必然上面这些绝对值数目和减1。所以有限步操作后必然达到均衡。所以现在唯一余下的问题就是如何计算这些数值问题。这个我们只要按照拓扑排序，从叶节点开始向根节点计算即可。

**casahama：**  
节点上的石头数不能小于0。所以当子节点石头数==0 并且 父节点石头数==0的时候，是需要继续向上回溯的。基于这一点，想在一次遍历中解决这个问题是不可能的。  
这一点考虑进去的话,看来应该再多加一个栈保存这样类似的结点才行.

**Torey：**  
后序遍历  
证明：  
在一棵只有三个节点的子二叉树里，石头在子树里搬运的步数肯定小于等于子树外面节点搬运的步数。  
石头由一个子树移到另一个子数可归结为两步，一为石头移到父节点，二为石头由父节点移到子树结点，所以无论哪颗石头移到哪个节点，总步数总是一定。

**关于树的遍历，在面试题中已出现过太多次了，特此稍稍整理以下：**  
二叉树结点存储的数据结构：  
typedef char datatype;  
typedef struct node  
 \{  
   datatype data;  
   struct node\* lchild,\*rchild;  
 \} bintnode;

typedef bintnode\* bintree;  
bintree root;

1.树的前序遍历即：  
按根 左 右 的顺序，依次  
前序遍历根结点->前序遍历左子树->前序遍历右子树

前序遍历，递归算法  
void preorder(bintree t)      
 //注，bintree为一指向二叉树根结点的指针  
\{  
   if(t)  
    \{  
      printf("%c",t->data);  
      preorder(t->lchild);  
      preorder(t->rchild);  
    \}  
\}

2.中序遍历，递归算法  
void preorder(bintree t)  
\{  
   if(t)  
    \{

inorder(t->lchild);  
      printf("%c",t->data);  
      inorder(t->rchild);  
    \}  
\}

3.后序遍历，递归算法  
void preorder(bintree t)  
\{  
   if(t)  
    \{

postorder(t->lchild);  
      postorder(t->rchild);  
      printf("%c",t->data);  
    \}  
\}

关于实现二叉树的前序、中序、后序遍历的递归与非递归实现，的更多，请参考这（微软100题第43题答案）：  
[http://blog.csdn.net/v\_JULY\_v/archive/2011/02/01/6171539.aspx][http_blog.csdn.net_v_JULY_v_archive_2011_02_01_6171539.aspx]。

**64**、淘宝校园笔试题  
goengine  
N个鸡蛋放到M个篮子中，篮子不能为空，要满足：对任意不大于N的数量，能用若干个篮子中鸡蛋的和表示。

写出函数，对输入整数N和M，输出所有可能的鸡蛋的放法。

比如对于9个鸡蛋5个篮子  
解至少有三组：  
1 2 4 1 1  
1 2 2 2 2  
1 2 3 2 1

**思路一、  
    Sorehead在我的微软100题，维护地址上，已经对此题有了详细的思路与阐释，以下是他的个人思路+代码：**  
Sorehead  
思路：  
    **1、**由于每个篮子都不能为空，可以转换成每个篮子先都有1个鸡蛋，再对剩下的N-M个鸡蛋进行分配，这样就可以先求和为N-M的所有排列可能性。  
    **2、**假设N-M=10，求解所有排列可能性可以从一个比较简单的递规来实现，转变为下列数组：  
(10,0)、(9,1)、(8,2)、(7,3)、(6,4)、(5,5)、(4,6)、(3,7)、(2,8)、(1,9)  
这里对其中第一个元素进行循环递减，对第二个元素进行上述递规重复求解，  
例如(5,5)转变成：(5,0)、(4,1)、(3,2)、(2,3)、(1,4)  
由于是求所有排列可能性，不允许有重复记录，因此结果就只能是非递增或者非递减队列，这里我采用的非递增队列来处理。  
    **3、**上面的递规过程中对于像(4,6)这样的不符合条件就可以跳过不输出，但递规不能直接跳出，必须继续进行下去，因为(4,6)的结果集中还是有不少能符合条件的。  
我写的是非递规程序，因此(4,6)这样的组合我就直接转换成4,4,2，然后再继续做处理。  
    **4、**N-M的所有排列可能性已经求出来了，里面的元素全部加1，如果N-M<M，剩下的元素就全部是1，这样N个鸡蛋放入M个篮子的所有可能性就全部求出来了。注意排列中可能元素数量会超过篮子数量M，去除这样的排列即可。

**5、**接下来的结果就是取出上述结果集中不满足“对于任意一个不超过N的正整数，都能由某几个篮子内蛋的数量相加得到”条件的记录了。  
首先是根据这个条件去除不可能有结果的情况：如果M>N，显而易见这是不可能有结果的；那对于给定的N值，M是否不能小于某个值呢，答案是肯定的。  
    **6、**对于给定的N值，M值最小的组合应该是1,2,4,8,16,32...这样的序列，这样我们就可以计算出M的最小值可能了，如果M小于该值，也是不可能有结果的。

**7、**接下来，对于给定的结果集，由于有个篮子的鸡蛋数量必须为1，可以先去掉最小值大于1的记录；同样，篮子中鸡蛋最大数量也应该不能超过某值，该值应该在N/2左右，具体值要看N是奇数还是偶数了，原因是因为超过这个值，其它篮子的鸡蛋数量全部相加都无法得到比该值小1的数。  
    **8、**最后如何保证剩下的结果中都是符合要求的，这是个难题。当然有个简单方法就是对结果中的每个数挨个进行判断。

1.  //下面是他写的代码：  
2.  **void** malloc\_egg(**int** m, **int** n)  
3.  \{  
4.      **int** \*stack, top;  
5.      **int** count, max, flag, i;  
6.    
7.      **if** (m < 1 || n < 1 || m > n)  
8.          **return**;  
9.    
10.     //得到m的最小可能值，去除不可能情况  
11.     i = n / 2;  
12.     count = 1;  
13.     **while** (i > 0)  
14.     \{  
15.         i /= 2;  
16.         count++;  
17.     \}  
18.     **if** (m < count)  
19.         **return**;  
20.   
21.     //对m=n或m=n-1进行特殊处理  
22.     **if** (m >= n - 1)  
23.     \{  
24.         **if** (m == n)  
25.             printf("1,");  
26.         **else**  
27.             printf("2,");  
28.         **for** (i = 0; i < m; i++)  
29.             printf("1,");  
30.         printf("/n");  
31.         **return**;  
32.     \}  
33.   
34.     **if** ((stack = malloc(**sizeof**(**int**) \* (n - m))) == NULL)  
35.         **return**;  
36.   
37.     stack\[0\] = n - m;  
38.     top = 0;  
39.   
40.     //得到篮子中鸡蛋最大数量值  
41.     max = n % 2 ? n / 2 : n / 2 - 1;  
42.     **if** (stack\[0\] <= max)  
43.     \{  
44.         printf("%d,", n - m + 1);  
45.         **for** (i = 1; i < m; i++)  
46.             printf("1,");  
47.         printf("/n");  
48.     \}  
49.   
50.     **do**  
51.     \{  
52.         count = 0;  
53.         **for** (i = top; i >= 0 && stack\[i\] == 1; i--)  
54.             count++;  
55.   
56.         **if** (count > 0)  
57.         \{  
58.             top -= count;  
59.             stack\[top\]--;  
60.             count++;  
61.             //保证是个非递增数列  
62.             **while** (stack\[top\] < count)  
63.             \{  
64.                 stack\[top + 1\] = stack\[top\];  
65.                 count -= stack\[top\];  
66.                 top++;  
67.             \}  
68.             stack\[++top\] = count;  
69.         \}  
70.         **else**  
71.         \{  
72.             stack\[top\]--;  
73.             stack\[++top\] = 1;  
74.         \}  
75.   
76.         //去除元素数量会超过篮子数量、超过鸡蛋最大数量值的记录  
77.         **if** (top >= m - 1)  
78.             **continue**;  
79.         **if** (stack\[0\] > max)  
80.             **continue**;  
81.   
82.         //对记录中的每个数挨个进行判断，保证符合条件二  
83.         flag = 0;  
84.         count = m - top;  
85.         **for** (i = top; i >= 0; i--)  
86.         \{  
87.             **if** (stack\[i\] >= count)  
88.             \{  
89.                 flag = 1;  
90.                 **break**;  
91.             \}  
92.             count += stack\[i\] + 1;  
93.         \}  
94.         **if** (flag)  
95.             **continue**;  
96.   
97.         //输出记录结果值  
98.         **for** (i = 0; i < m; i++)  
99.         \{  
100.             **if** (i <= top)  
101.                 printf("%d,", stack\[i\] + 1);  
102.             **else**  
103.                 printf("1,");  
104.         \}  
105.         printf("/n");  
106.     \}  
107.     **while** (stack\[0\] > 1);  
108.   
109.     free(stack);  
110. \}

存在的问题：  
    1、程序我没有进行严格的测试，所以不能保证中间没有问题，而且不少地方都可以再优化，中间有些部分处理得不是很好，有时间我再好好改进一下。  
    2、有些情况还可以特殊处理一下，例如M>N/2时，似乎满足条件一的所有组合都是满足条件二的；当N=(2的n次方-1)，M=n时，结果只有一个，就是1、2、4、...(2的n-1次方)，应该可以根据这个对其它结果进行推导。  
    3、这种方法是先根据条件一得到所有可能性，然后在这个结果集中去除不符合条件二的，感觉效率不是很好。个人觉得应该有办法可以直接把两个条件一起考虑，靠某种方式主动推出结果，而不是我现在采用的被动筛选方式。其实我刚开始就是想采用这种方式，但得到的结果集中总是缺少一些了排列可能。

**思路二、以下是晖的个人思路：**  
qq675927952  
    N个鸡蛋分到M个篮子里(N>M),不能有空篮子，对于任意不大于于N的数，保证有几个篮子的鸡蛋数和等于此数，编程实现输入N，M两个数，输出所有鸡蛋的方法。

**1、**全输出的话本质就是搜索+剪枝。  
    **2**、(n,m,min)表示当前状态，按照篮子里蛋的数目从小到大搜索。搜到了第m个篮子，1..m个篮子面共放了n个蛋，当前的篮子放了min个蛋。下一个扩展(n+t,m+1,t),for t=min...n+1。当n+(M-m)\*min>N (鸡蛋不够时)或者2^(M-m)\*n+2^(M-m)-1<N（鸡蛋太多）时　把这个枝剪掉…… 　；　  
    **3、**太多时的情况如下：　n,n+1,2n+2,4n+4,8n+8....。代码如下：

1.  //copyright@ 晖  
2.  //updated：  
3.  //听从网友yingmg的建议，再放到编译器上，调整下了缩进。  
4.  \#include <iostream>  
5.  **using** **namespace** std;  
6.  **long** pow2\[20\];  
7.  **int** N,M;  
8.  **int** ans\[1000\];  
9.  **void** solve( **int** n , **int** m , **int** Min )  
10. \{  
11.     **if**(n == N && m == M)  
12.     \{  
13.         **for**(**int** i=1;i<=M;i++)  
14.         \{  
15.             cout<<ans\[i\]<<" ";    
16.         \}   
17.         cout<<endl;  
18.         **return** ;    
19.     \}   
20.     **else** **if**( n + (M-m)\*Min > N || N > pow2\[M-m\]\*n + pow2\[M-m\]-1)  
21.         **return** ;  
22.     **else**  
23.     \{  
24.         **for**(**int** i = Min; i <= n+1; i++)  
25.         \{  
26.             ans\[m+1\] =  i;      
27.             solve(n+i,m+1,i);   
28.         \}   
29.           
30.     \}   
31. \}  
32.   
33. **int** main()  
34. \{  
35.     pow2\[0\] = 1;  
36.     **for**(**int** i=1;i<20;i++)  
37.     \{  
38.         pow2\[i\] = pow2\[i-1\]<<1;    
39.     \}  
40.     cin>>N>>M;  
41.     **if**( M > N || pow2\[M\]-1 < N)  
42.     \{  
43.         cout<<"没有这样的组合"<<endl;     
44.     \}     
45.     solve( 0 , 0 , 1 );  
46.     system("pause");   
47.     **return** 0;   
48. \}

此思路二来自： [http://blog.csdn.net/qq675927952/archive/2011/03/30/6290131.aspx][http_blog.csdn.net_qq675927952_archive_2011_03_30_6290131.aspx]。  
  
**65**、华为面试  
qq5823996  
char \*str = "AbcABca";  
写出一个函数，查找出每个字符的个数，区分大小写，要求时间复杂度是n（提示用ASCⅡ码）

很基础，也比较简单的一题，看下这位网友给的代码吧：  
**nlqlove：**

1.  \#include <stdio.h>  
2.    
3.  **int** main(**int** argc, **char**\*\* argv)  
4.  \{  
5.      **char** \*str = "AbcABca";  
6.      **int** count\[256\] = \{0\};  
7.    
8.      **for** (**char** \*p=str; \*p; p++)  
9.      \{  
10.         count\[\*p\]++;  
11.     \}  
12.   
13.     // print  
14.     **for** (**int** i=0; i<256; i++)  
15.     \{  
16.         **if** (count\[i\] > 0)  //有个数大于零的，就打印出来  
17.         \{  
18.             printf("The count of %c is: %d/n",i, count\[i\]);  
19.         \}  
20.     \}  
21.     **return** 0;  
22. \}

**66**、微软面试题  
yaoha2003  
请把一个整形数组中重复的数字去掉。例如：   
1,   2,   0,   2,   -1,   999,   3,   999,   88   
答案应该是：   
1,   2，   0，   -1，   999，   3，   88

**67**、请编程实现全排列算法。  
全排列算法有两个比较常见的实现：递归排列和字典序排列。

yysdsyl：  
**（1）递归实现**  
从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，从而

得到所有元素的全排列。算法实现如下：

1.  \#include <iostream>  
2.  \#include <algorithm>  
3.  **using** **namespace** std;  
4.    
5.  **template** <**typename** T>  
6.  **void** CalcAllPermutation\_R(T perm\[\], **int** first, **int** num)  
7.  \{  
8.      **if** (num <= 1) \{  
9.          **return**;  
10.     \}  
11.       
12.     **for** (**int** i = first; i < first + num; ++i) \{  
13.         swap(perm\[i\], perm\[first\]);  
14.         CalcAllPermutation\_R(perm, first + 1, num - 1);  
15.         swap(perm\[i\], perm\[first\]);  
16.     \}  
17. \}  
18.   
19. **int** main()  
20. \{  
21.     **const** **int** NUM = 12;  
22.     **char** perm\[NUM\];  
23.       
24.     **for** (**int** i = 0; i < NUM; ++i)  
25.         perm\[i\] = 'a' + i;  
26.       
27.     CalcAllPermutation\_R(perm, 0, NUM);  
28. \}

程序运行结果（优化）：  
\-bash-3.2$ g++ test.cpp -O3 -o ttt  
\-bash-3.2$ time ./ttt

real    0m10.556s  
user    0m10.551s  
sys     0m0.000s

程序运行结果（不优化）：  
\-bash-3.2$ g++ test.cpp -o ttt  
\-bash-3.2$ time ./ttt

real    0m21.355s  
user    0m21.332s  
sys     0m0.004s

**（2）字典序排列**  
把升序的排列（当然，也可以实现为降序）作为当前排列开始，然后依次计算当前排列的下一个字典序排列。

对当前排列从后向前扫描，找到一对为升序的相邻元素，记为i和j（i < j）。如果不存在这样一对为升序的相邻元素，则所有排列均已找到，算法结束；否则，重新对当前排列从后向前扫描，找到第一个大于i的元素k，交换i和k，然后对从j开始到结束的子序列反转，则此时得到的新排列就为下一个字典序排列。这种方式实现得到的所有排列是按字典序有序的，这也是C++ STL算法next\_permutation的思想。算法实现如下：

1.  \#include <iostream>  
2.  \#include <algorithm>  
3.  **using** **namespace** std;  
4.    
5.  **template** <**typename** T>  
6.  **void** CalcAllPermutation(T perm\[\], **int** num)  
7.  \{  
8.      **if** (num < 1)  
9.          **return**;  
10.           
11.     **while** (**true**) \{  
12.         **int** i;  
13.         **for** (i = num - 2; i >= 0; --i) \{  
14.             **if** (perm\[i\] < perm\[i + 1\])  
15.                 **break**;  
16.         \}  
17.           
18.         **if** (i < 0)  
19.             **break**;  // 已经找到所有排列  
20.       
21.         **int** k;  
22.         **for** (k = num - 1; k > i; --k) \{  
23.             **if** (perm\[k\] > perm\[i\])  
24.                 **break**;  
25.         \}  
26.           
27.         swap(perm\[i\], perm\[k\]);  
28.         reverse(perm + i + 1, perm + num);  
29.           
30.     \}  
31. \}  
32.   
33. **int** main()  
34. \{  
35.     **const** **int** NUM = 12;  
36.     **char** perm\[NUM\];  
37.       
38.     **for** (**int** i = 0; i < NUM; ++i)  
39.         perm\[i\] = 'a' + i;  
40.       
41.     CalcAllPermutation(perm, NUM);  
42. \}

程序运行结果（优化）：  
\-bash-3.2$ g++ test.cpp -O3 -o ttt  
\-bash-3.2$ time ./ttt

real    0m3.055s  
user    0m3.044s  
sys     0m0.001s

程序运行结果（不优化）：  
\-bash-3.2$ g++ test.cpp -o ttt  
\-bash-3.2$ time ./ttt

real    0m24.367s  
user    0m24.321s  
sys     0m0.006s

使用std::next\_permutation来进行对比测试，代码如下：

1.  \#include <iostream>  
2.  \#include <algorithm>  
3.  **using** **namespace** std;  
4.    
5.  **template** <**typename** T>  
6.  **size\_t** CalcAllPermutation(T perm\[\], **int** num)  
7.  \{  
8.      **if** (num < 1)  
9.          **return** 0;  
10.           
11.     **size\_t** count = 0;  
12.     **while** (next\_permutation(perm, perm + num)) \{  
13.         ++count;  
14.           
15.     \}  
16.       
17.     **return** count;  
18. \}  
19.   
20. **int** main()  
21. \{  
22.     **const** **int** NUM = 12;  
23.     **char** perm\[NUM\];  
24.       
25.     **for** (**int** i = 0; i < NUM; ++i)  
26.         perm\[i\] = 'a' + i;  
27.       
28.     **size\_t** count = CalcAllPermutation(perm, NUM);  
29.       
30.     **return** count;  
31. \}

程序运行结果（优化）：  
\-bash-3.2$ g++ test.cpp -O3 -o ttt  
\-bash-3.2$ time ./ttt

real    0m3.606s  
user    0m3.601s  
sys     0m0.002s

程序运行结果（不优化）：  
\-bash-3.2$ g++ test.cpp -o ttt  
\-bash-3.2$ time ./ttt

real    0m33.850s  
user    0m33.821s  
sys     0m0.006s

测试结果汇总一（优化）：  
（1）递归实现：0m10.556s  
（2-1）字典序实现：0m3.055s  
（2-2）字典序next\_permutation：0m3.606s

测试结果汇总二（不优化）：  
（1）递归实现：0m21.355s  
（2-1）字典序实现：0m24.367s  
（2-2）字典序next\_permutation：0m33.850s

**由测试结果可知**，自己实现的字典序比next\_permutation稍微快点，原因可能是next\_permutation版本有额外的函数调用开销；而归实现版本在优化情况下要慢很多，主要原因可能在于太多的函数调用开销，但在不优化情况下执行比其它二个版本要快，原因可能在于程序结构更简单，执行的语句较少。

比较而言，递归算法结构简单，适用于全部计算出所有的排列（因此排列规模不能太大，计算机资源会成为限制）；而字典序排列逐个产生、处理排列，能够适用于大的排列空间，并且它产生的排列的规律性很强。

**68**、阿里巴巴三道面试题  
fenglibing  
1、澳大利亚的父母喜欢女孩，如果生出来的第一个女孩，就不再生了，如果是男孩就继续生，直到生到第一个女孩为止，问若干年后，男女的比例是多少？  
2、3点15的时针和分针的夹角是多少度  
3、有8瓶水，其中有一瓶有毒，最少尝试几次可以找出来

**69**、阿里巴巴2011实习生笔试题  
 给一篇文章，里面是由一个个单词组成，单词中间空格隔开，再给一个字符串指针数组，  
比如 char \*str\[\]=\{"hello","world","good"\};  
求文章中包含这个字符串指针数组的最小子串。注意，只要包含即可，没有顺序要求。

分析：文章也可以理解为一个大的字符串数组，单词之前只有空格，没有标点符号。

我最开始想到的思路，是：  
**维护 一个队列+KMP算法**  
让字符的全部序列入队，比较完一个就出队，保持长度  
至于字符串的六种序列，实现排列预处理，  
最后，时间复杂度为：O（字符事先排列）+O（KMP 比较）。

后来，本BLOG算法交流群内有人提出：  
Sur鱼：  
这个用kmp算法的话,明显不如用**trie**好;  
将str 中的成员建一棵trie树,这样的话字符事先不需要排序,复杂度应该低些。  
梦想天窗：  
我觉得这个应该用**DFA**（即有限状态自动机）。

**70**、Google算法笔试题  
有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占 R\[i\]个空间，储存计算结果则需要占据O\[i\]个空间（据O\[i\]个空间（其中O\[i\]<R\[i\]）。问怎么安排这n个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。比方说，m=14，n=2，R\[1\]=10，O\[1\]=5，R\[2\]=8，O\[2\]=6。在这个例子中，我们可以先运行第一个任务，剩余9个单位的空间足够执行第二个任务；但如果先走第二个任务，第一个任务执行时空间就不够了，因为10>14-6。

**matrix67：**  
当时花了全部的时间去想各种网络流、费用流、图的分层思想等等，最后写了一个铁定错误的贪心上去。直到考试结束4个小时以后我才想到了正确的算法——只需要按照R值和O值之差（即释放空间的大小）从大到小排序，然后依次做就是了……

**Z.Hao：**  
此算法题曾是交大09年招保研生的复试题。Matrix67给出的算法是不完整的。

某日阳光明媚下午曾和petercai共同商讨过，应该是先对驻留内存进行排序，  
选择驻留内存最小的里面可以在当前内存中运行且（运行内存-驻留内存）最小的进行调度。  
但是这种算法显然仍然仅仅不够..此题目前还有容考虑。

若各位想到更好的思路，或者以上任何一题的思路或答案有任何问题，欢迎不吝指正。  
完。

**updated：**  
本文评论中，qiquanchang、hellorld俩位网友指出：此第七十题是死锁检测算法，银行家算法。  
非常感谢，俩位的指导。多谢。

update again：  
如果你对以上任何一代的思路，有任何问题，欢迎在留言或评论中告知。如果您对以上任何一题，有更好的代码或思路，欢迎发到我的第二个邮箱，[786165179@qq.com][786165179_qq.com]。若经采纳，将更新到本文中，非常感谢。

July、2011..4.17。

[http_weibo.com_julyweibo]: http://weibo.com/julyweibo
[http_blog.csdn.net_v_JULY_v]: http://blog.csdn.net/v_JULY_v
[100_1-60]: http://blog.csdn.net/v_JULY_v/archive/2011/03/09/6234496.aspx
[100]: http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx
[Csdn _100]: http://blog.csdn.net/v_JULY_v/archive/2010/11/17/6015165.aspx
[http_blog.csdn.net_v_JULY_v_archive_2011_02_01_6171539.aspx]: http://blog.csdn.net/v_JULY_v/archive/2011/02/01/6171539.aspx
[http_blog.csdn.net_qq675927952_archive_2011_03_30_6290131.aspx]: http://blog.csdn.net/qq675927952/archive/2011/03/30/6290131.aspx
[786165179_qq.com]: mailto:786165179@qq.com