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

Myth丶恋晨 2022-08-10 12:47 137阅读 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. **usingnamespace std;** 
11. 
12. **int scan(constchar\* text, constchar\* pattern)** 
13. **\{** 
14. **constchar \*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 = newchar\[100\];** 
43.  **j = newchar\[100\];** 
44.  **cin>>i>>j;** 
45.  **cout<<scan(i,j);** 
46. **return 0;** 
47. **\}**

**代码二：**

1.  **//qq120848369：**
2.  **\#include <iostream>**
3.  **usingnamespace std;** 
4.  **constchar \*pEnd=NULL;** 
5.  
6.  **bool match(constchar \*pszText,constchar \*pszName)** 
7.  **\{** 
8.  **if(\*pszName == '/0') // 匹配完成**
9.   **\{** 
10.  **pEnd=pszText;** 
11. **returntrue;** 
12.  **\}** 
13. 
14. **if(\*pszText == '/0') // 未匹配完成**
15.  **\{** 
16. **if(\*pszName == '\*')** 
17.  **\{** 
18.  **pEnd=pszText;** 
19. **returntrue;** 
20.  **\}** 
21. 
22. **returnfalse;** 
23.  **\}** 
24. 
25. **if(\*pszName!= '\*' && \*pszName!='?')** 
26.  **\{** 
27. **if(\*pszText == \*pszName)** 
28.  **\{** 
29. **return match(pszText+1,pszName+1);** 
30.  **\}** 
31. 
32. **returnfalse;** 
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(constchar \*pszText, constchar \*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.  **usingnamespace 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. **elseif(\*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.  **usingnamespace std;** 
4.  
5.  **bool findSame(constint \*a,int len1,constint \*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. **elseif(a\[i\]>b\[j\])** 
17.  **\{** 
18.  **++j;** 
19.  **\}** 
20. **else**
21.  **\{** 
22.  **\*result=a\[i\];** 
23. **returntrue;** 
24.  **\}** 
25.  **\}** 
26. **returnfalse;** 
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.  **usingnamespace 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