永久勘误:微软等面试100题答案V0.3版[第21-40题答案]

淩亂°似流年 2021-12-01 23:54 208阅读 0赞

**微软等面试100题****答案V0.****3****版第21-40题****部分答案精选**

**作者:July 、何海涛等网友**

\-------------------------------------

开诚布公，接受读者质检

本文，是根据我之前上传的，微软等面试100题，的答案V0.3版\[第21-40题答案\]的部分答案精选，  
而写。

现在，原版答案V0.3版公布出来，接受读者检验。

**此文永久勘误、永久优化。**同时，希望，各位不吝指正。谢谢。

===========

本微软等100题系列V0.1版，永久维护（网友，思路回复）地址：  
[http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html][http_topic.csdn.net_u_20101126_10_b4f12a00-6280-492f-b785-cb6835a63dc9.html]

ok。

\-----------------------

**第21题**  
2010年中兴面试题  
编程求解：  
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,  
使其和等于 m ,要求将其中所有的可能组合列出来.  
//此题与第14题差不多，在次不做过多解释。  
//July、本程序，经网友指出有误，但暂时没有想到解决的办法。见谅。2010/10/22。

**    updated：第20题首次勘误，请参见第749、750、751楼（已经测试正确，后续将具体分析与优化）：**[http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9\_8.html][http_topic.csdn.net_u_20101126_10_b4f12a00-6280-492f-b785-cb6835a63dc9_8.html]。有任何问题，欢迎任何朋友随时指出。二零一一年四月二十日，July，updated。

1.  // 21题递归方法  
2.  //这个，没有任何问题  
3.  //from yansha  
4.  //July、updated。  
5.  \#include<list>  
6.  \#include<iostream>  
7.  **using** **namespace** std;  
8.    
9.  list<**int**>list1;  
10. **void** find\_factor(**int** sum, **int** n)   
11. \{  
12.     // 递归出口  
13.     **if**(n <= 0 || sum <= 0)  
14.         **return**;  
15.       
16.     // 输出找到的结果  
17.     **if**(sum == n)  
18.     \{  
19.         // 反转list  
20.         list1.reverse();  
21.         **for**(list<**int**>::iterator iter = list1.begin(); iter != list1.end(); iter++)  
22.             cout << \*iter << " + ";  
23.         cout << n << endl;  
24.         list1.reverse();      
25.     \}  
26.       
27.     list1.push\_front(n);      //典型的01背包问题  
28.     find\_factor(sum-n, n-1);   //放n，n-1个数填满sum-n  
29.     list1.pop\_front();  
30.     find\_factor(sum, n-1);     //不放n，n-1个数填满sum   
31. \}  
32.   
33. **int** main()  
34. \{  
35.     **int** sum, n;  
36.     cout << "请输入你要等于多少的数值sum:" << endl;  
37.     cin >> sum;  
38.     cout << "请输入你要从1.....n数列中取值的n：" << endl;  
39.     cin >> n;  
40.     cout << "所有可能的序列，如下：" << endl;  
41.     find\_factor(sum,n);  
42.     **return** 0;  
43. \}

**第22题：**  
有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，  
再分别在A、B、C三人额头上贴任意两张牌，

A、B、C三人都可以看见其余两人额头上的牌，  
看完后让他们猜自己额头上是什么颜色的牌，  
A说不知道，B说不知道，C说不知道，然后A说知道了。

请教如何推理，A是怎么知道的。如果用程序，又怎么实现呢？

//July、2010/10/22  
//今是老妈生日，祝福老妈，生日快乐。!:).

4张 r 4张b  
有以下3种组合：  
rr bb rb

1.B，C全是一种颜色   
B         C       A  
bb.rr    bb.rr

2.  
B        C        A  
bb       rr       bb/RR/BR,=>A:BR  
rr       bb       =>A:BR

3.  
B        C        A  
BR       BB       RR/BR,   =>A:BR  
//推出A:BR的原因，  
//如果       A是 RR，  
//那么，当ABC都说不知道后，B 最后应该知道自己是BR了。  
//因为B 不可能 是 RR或BB。

4.  
B        C        A  
BR       BR       BB/RR/BR  
//推出A:BR的原因  
//**i、** 如果，A是 BB，那么B=>BR/RR，  
//如果B=>RR,那么一开始，C就该知道自己是BR了（A俩蓝，B俩红）。（如果C.A俩蓝，那么B就一开始知道,如果C.B俩红，那么A一开始就知道，所以，论证前头，当B=>RR，那么一开始，C就该知道自己是BR）。  
//如果B=>BR,那么，同样道理，C一开始也该知道自己是BR了。

//**ii、** 如果A是RR....

//**iii、**最后，也还是推出=>A:BR  
//至于程序，暂等高人。

**第24题：反转链表**  
pPrev<-pNode<-pNext

ListNode\* ReverseIteratively(ListNode\* pHead)  
\{  
      ListNode\* pReversedHead = NULL;  
      ListNode\* pNode = pHead;  
      ListNode\* pPrev = NULL;  
      while(pNode != NULL)         //pNode<=>m  
      \{  
            ListNode\* pNext = pNode->m\_pNext;       //n保存在pNext下

//如果pNext指为空，则当前结点pNode设为头。  
            if(pNext == NULL)  
                  pReversedHead = pNode;

// reverse the linkage between nodes  
            pNode->m\_pNext = pPrev;

// move forward on the the list  
            pPrev = pNode;  
            pNode = pNext;  
      \}  
      return pReversedHead;  
\}

或者，这样写：  
**head->next** -> **p**\-> **q**

template<class T>  
Node<T>\* Reverse(Node<T>\* head)  
\{  
  p=head->next;  
  while(p)  
  \{  
     q=p->next;           //p->next先保存在q下  
      p->next=head->next;  //p掉头指向head->next  
     head->next=p;        //p赋给head->next  
     p=q;                 //q赋给p。  
                          //上俩行即，指针前移嘛...  
  \}  
  return head;

**第25题：**  
写一个函数,它的原形是int continumax(char \*outputstr,char \*intputstr)  
功能：  
在字符串中找出连续最长的数字串，并把这个串的长度返回，  
并把这个最长数字串付给其中一个函数参数outputstr所指内存。  
例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回9，  
outputstr所指的值为123456789

//leeyunce  
这个相对比较简单，思路不用多说，跟在序列中求最小值差不多。未经测试。有错误欢迎指出。

int continumax(char \*outputstr, char \*intputstr)  
\{  
    int i, maxlen = 0;  
    char \* maxstr = 0;

while (true)  
    \{      
        while (intputstr && (\*intputstr<'0' || \*intputstr>'9')) //skip all non-digit

characters  
        \{      
            intputstr++;  
        \}

if (!intputstr) break;

int count = 0;  
        char \* tempstr = intputstr;  
        while (intputstr && (\*intputstr>='0' && \*intputstr<='9')) //OK, these characters are

digits  
        \{      
            count++;  
            intputstr++;  
        \}  
        if (count > maxlen)  
        \{      
            maxlen = count;  
            maxstr = tempstr;  
        \}  
    \}

for (i=0; i<maxlen; i++)  
    \{      
        outputstr\[i\] = maxstr\[i\];  
    \}

outputstr\[i\] = 0;

return maxlen;  
\}

**26.左旋转字符串**  
  题目：  
  定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。  
    如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。  
    要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。

分析：如果不考虑时间和空间复杂度的限制，  
最简单的方法莫过于把这道题看成是把字符串分成前后两部分，  
通过旋转操作把这两个部分交换位置。

于是我们可以新开辟一块长度为n+1的辅助空间，  
把原字符串后半部分拷贝到新空间的前半部分，在把原字符串的前半部分拷贝到新空间的后半部分。  
不难看出，这种思路的时间复杂度是O(n)，需要的辅助空间也是O(n)。

把字符串看成有两段组成的，记位XY。左旋转相当于要把字符串XY变成YX。  
我们先在字符串上定义一种翻转的操作，就是翻转字符串中字符的先后顺序。把X翻转后记为XT。显然有

(XT)T=X。  
我们首先对X和Y两段分别进行翻转操作，这样就能得到XTYT。  
接着再对XTYT进行翻转操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我们期待的结果。

分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段，  
第一段为前面m个字符，其余的字符分到第二段。  
再定义一个翻转字符串的函数，按照前面的步骤翻转三次就行了。  
时间复杂度和空间复杂度都合乎要求。

\#include "string.h"

// Move the first n chars in a string to its end   
char\* LeftRotateString(char\* pStr, unsigned int n)  
\{  
    if(pStr != NULL)  
    \{  
        int nLength = static\_cast<int>(strlen(pStr));  
        if(nLength > 0 || n == 0 || n > nLength)  
        \{  
            char\* pFirstStart = pStr;  
            char\* pFirstEnd = pStr + n - 1;  
            char\* pSecondStart = pStr + n;  
            char\* pSecondEnd = pStr + nLength - 1;  
              
            // reverse the first part of the string  
            ReverseString(pFirstStart, pFirstEnd);  
            // reverse the second part of the strint  
            ReverseString(pSecondStart, pSecondEnd);  
            // reverse the whole string  
            ReverseString(pFirstStart, pSecondEnd);  
        \}  
    \}  
      
    return pStr;  
\}

// Reverse the string between pStart and pEnd  
void ReverseString(char\* pStart, char\* pEnd)  
\{  
    if(pStart == NULL || pEnd == NULL)  
    \{  
        while(pStart <= pEnd)  
        \{  
            char temp = \*pStart;  
            \*pStart = \*pEnd;  
            \*pEnd = temp;  
              
            pStart ++;  
            pEnd --;  
        \}  
    \}  
\}

========================

**针对262 楼 litaoye 的回复：  
26.**左旋转字符串  
跟panda所想，是一样的，即，  
以abcdef为例  
1. ab->ba  
2. cdef->fedc  
原字符串变为bafedc  
3. 整个翻转：cdefab    
  //时间复杂度为O（n）  
  
在此，奉献另外一种思路：  
abc defghi，要abc移动至最后  
abc defghi->def abcghi->def ghiabc  
  
一俩指针，p1指向ch\[0\]，p2指向\[ch m-1\]，  
p2每次移动m 的距离，p1 也跟着相应移动，  
  
每次移动过后，交换。  
如上第一步，交换abc 和def ，就变成了 abcdef->defabc  
  
第一步，  
abc defghi->def abcghi  
第二步，继续交换，  
def abcghi->def ghiabc  
  
整个过程，看起来，就是abc 一步一步 向后移动  
abc defghi  
def abcghi  
def ghi abc    
  //最后的 复杂度是O（m+n）    
  
再举一个例子，  
如果123 4567890要变成4567890 123：  
  123 4567890  
1. 456 123 7890  
2. 456789 123 0  
3. 456789 12 0 3  
4. 456789 1 0 23  
5. 4567890 123 //最后三步，相当于0前移，p1已经不动。  
  欢迎，就此第26题，继续讨论。

**二零一一年一月十七日补正。**  
=============================================

**27.跳台阶问题**  
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。  
求总共有多少总跳法，并分析算法的时间复杂度。

首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。  
如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。

现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。  
当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，  
此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；  
另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。  
因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。

我们把上面的分析用一个公式总结如下：

/  1                          n=1  
f(n)=      2                          n=2  
        /  f(n-1)+(f-2)               n>2

分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。

int jump\_sum(int n)  //递归版本  
\{  
    assert(n>0);  
    if (n == 1 || n == 2) return n;  
    return jump\_sum(n-1)+jump\_sum(n-2);  
\}

int jump\_sum(int n) //迭代版本  
\{  
    assert(n>0);  
    if (n == 1 || n == 2) return n;

int an, an\_1=2, an\_2=1;  
    for (; n>=3; n--)  
    \{      
        an = an\_2 + an\_1;  
        an\_2 = an\_1;  
        an\_1 = an;  
    \}  
    return an;  
\}

**28.整数的二进制表示中1的个数**  
题目：输入一个整数，求该整数的二进制表达中有多少个1。  
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。

分析：  
这是一道很基本的考查位运算的面试题。  
包括微软在内的……

一个很基本的想法是，我们先判断整数的最右边一位是不是1。  
接着把整数右移一位，原来处于右边第二位的数字现在被移到第一位了，  
再判断是不是1。  
这样每次移动一位，直到这个整数变成0为止。  
现在的问题变成怎样判断一个整数的最右边一位是不是1了。

很简单，如果它和整数1作与运算。由于1除了最右边一位以外，其他所有位都为0。  
因此如果与运算的结果为1，表示整数的最右边一位是1，否则是0。\*/

得到的代码如下：

///  
// Get how many 1s in an integer's binary expression  
///  
int NumberOf1\_Solution1(int i)  
\{  
      int count = 0;  
      while(i)  
      \{  
            if(i & 1)  
                  count ++;

i = i >> 1;  
      \}

return count;  
\}

可能有读者会问，整数右移一位在数学上是和除以2是等价的。  
那可不可以把上面的代码中的右移运算符换成除以2呢？答案是最好不要换成除法。  
因为除法的效率比移位运算要低的多，  
在实际编程中如果可以应尽可能地用移位运算符代替乘除法。

这个思路当输入i是正数时没有问题，但当输入的i是一个负数时，  
不但不能得到正确的1的个数，还将导致死循环。

以负数0x80000000为例，右移一位的时候，  
并不是简单地把最高位的1移到第二位变成0x40000000，  
而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，  
因此移位后的最高位会设为1。  
如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。

为了避免死循环，我们可以不右移输入的数字i。  
首先i和1做与运算，判断i的最低位是不是为1。  
接着把1左移一位得到2，再和i做与运算，就能判断i的次高位是不是1……  
这样反复左移，每次都能判断i的其中一位是不是1。基于此，我们得到如下代码：

///  
// Get how many 1s in an integer's binary expression  
///  
int NumberOf1\_Solution2(int i)  
\{  
      int count = 0;  
      unsigned int flag = 1;  
      while(flag)  
      \{  
            if(i & flag)  
                  count ++;

flag = flag << 1;  
      \}

return count;  
\}

**29.栈的push、pop序列**  
题目：输入两个整数序列。其中一个序列表示栈的push顺序，  
判断另一个序列有没有可能是对应的pop顺序。

如果我们希望pop的数字正好是栈顶数字，直接pop出栈即可；  
如果希望pop的数字目前不在栈顶，我们就到  
push序列中还没有被push到栈里的数字中去搜索这个数字，  
并把在它之前的所有数字都push进栈。  
如果所有的数字都被push进栈仍然没有找到这个数字，表明该序列不可能是一个pop序列。  
  
我们来着重分析下此题：  
push序列已经固定，  
  push              pop  
\--- -- ->            /---->     
5 4 3 2 1           /     4 5 3 2 1   
            |   5  |  
            |   4  |  
            |   3  |  
            |   2  |  
            |\_\_\_1\_\_|

1.要得到4 5 3 2 1的pop序列，即pop的顺序为4->5->3->2->1  
首先，要pop4，可让push5 之前，pop4，然后push5，pop5  
然后发现3在栈顶，直接pop 3..2..1

2.再看一序列，  
  push              pop  
\--- -- ->            /---->     
5 4 3 2 1           /     4 3 5 1 2   
            |   5  |  
            |   4  |  
            |   3  |  
            |   2  |  
            |\_\_\_1\_\_|  
想得到4 3 5 1 2的pop序列，是否可能?      4->3->5->1->2    
同样在push5之前，push 了 4 3 2 1，pop4，pop 3，然后再push 5，pop5  
                     2  
再看栈中的从底至上是 1 ，由于1 2已经在栈中，所以只能先pop2，才能pop1。  
所以，很显然，不可能有 4 3 5 1 2的 pop序列。

所以上述那段注释的话的意思，即是，  
如果，一个元素在栈顶，直接pop即可。如果它不在栈顶，那么从push序列中找这个元素  
找到，那么push 它，然后再 pop 它。否则，无法在 那个顺序中 pop。

//  
push序列已经固定，  
  push              pop  
\--- -- ->            /---->     
5 4 3 2 1           /     3 5 4 2 1  //可行   
            |   5  |      1 4 5 3 2  //亦可行，不知各位，是否已明了题意?:)..  
            |   4  |  
            |   3  |  
            |   2  |  
            |\_\_\_1\_\_|

///  
今早我也来了，呵。  
昨晚，后来，自个又想了想，要怎么才能pop想要的一个数列?  
push序列已经固定，  
  push              pop  
\--- -- ->            /---->     
5 4 3 2 1           /     5 4 3 2 1   
            |   5  |  
            |   4  |  
            |   3  |  
            |   2  |  
            |\_\_\_1\_\_|

比如，当栈中已有数列  2  
                   1  
而现在我随机 要 pop4，一看，4不在栈中，再从push序列中，  
正好，4在push队列中，push4进栈之前，还得把 4前面的数，即3 先push进来，。  
好，现在，push 3, push 4，然后便是想要的结果：pop 4。

所以，当我要pop 一个数时，先看这个数 在不在已经push的 栈顶，如果，在，好，直接pop它。  
如果，不在，那么，从 push序列中，去找这个数，找到后，push 它进栈，  
如果push队列中它的前面还有数，那么 还得把它前面数，先push进栈。  
如果铺设队列中没有这个数，那当然 就不是存在这个 pop 结果了。

不知，我说明白了没?：）.接下来，给一段，参考程序：

//有误之处，恳请指正。July、2010/11/09。:)。  
bool IsPossiblePopOrder(const int\* pPush, const int\* pPop, int nLength)  
\{  
      bool bPossible = false;

if(pPush && pPop && nLength > 0)  
      \{  
            const int \*pNextPush = pPush;  
            const int \*pNextPop = pPop;

// ancillary stack  
            std::stack<int> stackData;

// check every integers in pPop  
            while(pNextPop - pPop < nLength)  
            \{  
                  // while the top of the ancillary stack is not the integer   
                  // to be poped, try to push some integers into the stack  
                  while(stackData.empty() || stackData.top() != \*pNextPop)  
                  \{  
                        // pNextPush == NULL means all integers have been   
                        // pushed into the stack, can't push any longer  
                        if(!pNextPush)  
                              break;

stackData.push(\*pNextPush);

// if there are integers left in pPush, move   
                        // pNextPush forward, otherwise set it to be NULL  
                        if(pNextPush - pPush < nLength - 1)  
                              pNextPush ++;  
                        else  
                              pNextPush = NULL;  
                  \}

// After pushing, the top of stack is still not same as   
                  // pPextPop, pPextPop is not in a pop sequence  
                  // corresponding to pPush  
                  if(stackData.top() != \*pNextPop)  
                        break;

// Check the next integer in pPop  
                  stackData.pop();  
                  pNextPop ++;  
            \}

// if all integers in pPop have been check successfully,   
            // pPop is a pop sequence corresponding to pPush   
            if(stackData.empty() && pNextPop - pPop == nLength)  
                  bPossible = true;  
      \}

return bPossible;  
\}

**30.在从1到n的正数中1出现的次数**  
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。  
分析：这是一道广为流传的google面试题。

我们每次判断整数的个位数字是不是1。如果这个数字大于10，除以10之后再判断个位数字是不是1。  
基于这个思路，不难写出如下的代码：\*/

int NumberOf1(unsigned int n);

int NumberOf1BeforeBetween1AndN\_Solution1(unsigned int n)  
\{  
      int number = 0;

// Find the number of 1 in each integer between 1 and n  
      for(unsigned int i = 1; i <= n; ++ i)  
            number += NumberOf1(i);

return number;  
\}

int NumberOf1(unsigned int n)  
\{  
      int number = 0;  
      while(n)  
      \{  
            if(n % 10 == 1)  
                  number ++;

n = n / 10;  
      \}

return number;  
\}

这个思路有一个非常明显的缺点就是每个数字都要计算1在该数字中出现的次数，因此时间复杂度是O(n)。  
当输入的n非常大的时候，需要大量的计算，运算效率很低。

各位，不妨讨论下，更好的解决办法。:)...

\---------------------------  
第30题，网友love8909给的思路：  
char num\[16\];

int len, dp\[16\]\[16\]\[2\];

int dfs(int pos, int ct, int less)  
\{  
 if (pos == len)

return ct;  
 int &ret = dp\[pos\]\[ct\]\[less\];  
 if (ret != -1)

return ret;

ret = 0;  
 for (int d = 0; d <= (less ? 9 : num\[pos\] - '0'); d++)  
  ret += dfs(pos + 1, ct + (d == 1), less || d < num\[pos\] - '0');

return ret;  
\}

int NumOf1(int n)  
\{  
 sprintf(num, "%d", n);  
 len = strlen(num);  
 memset(dp, 0xff, sizeof(dp));  
 return dfs(0, 0, 0);  
\}

**希望，更多的人，提出优化方案。**

==========

**32.**  
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；  
要求：通过交换a,b中的元素，使\[序列a元素的和\]与\[序列b元素的和\]之间的差最小。  
例如:   
var a=\[100,99,98,1,2, 3\];  
var b=\[1, 2, 3, 4,5,40\];

求解思路：  
    当前数组a和数组b的和之差为  
    A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，a和b的和之差为  
    A' = sum(a) - a\[i\] + b\[j\] - （sum(b) - b\[j\] + a\[i\])  
           = sum(a) - sum(b) - 2 (a\[i\] - b\[j\])  
           = A - 2 (a\[i\] - b\[j\])

设x = a\[i\] - b\[j\]  
    |A| - |A'| = |A| - |A-2x|

假设A > 0,  
    当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，  
x越接近A/2效果越好,  
    如果找不到在(0,A)之间的x，则当前的a和b就是答案。

所以算法大概如下：  
    在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，  
重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。

/  
算法  
1. 将两序列合并为一个序列，并排序，为序列Source   
2. 拿出最大元素Big，次大的元素Small   
3. 在余下的序列S\[:-2\]进行平分，得到序列max，min   
4. 将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max，小的为min。

def mean( sorted\_list ):  
    if not sorted\_list:  
        return ((\[\],\[\]))  
   
    big = sorted\_list\[-1\]  
    small = sorted\_list\[-2\]  
    big\_list, small\_list = mean(sorted\_list\[:-2\])  
   
    big\_list.append(small)  
    small\_list.append(big)  
   
    big\_list\_sum = sum(big\_list)  
    small\_list\_sum = sum(small\_list)  
   
    if big\_list\_sum > small\_list\_sum:  
        return ( (big\_list, small\_list))  
    else:  
        return (( small\_list, big\_list))  
   
tests = \[   \[1,2,3,4,5,6,700,800\],  
            \[10001,10000,100,90,50,1\],  
            range(1, 11),  
            \[12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1\]  
            \]  
for l in tests:  
    l.sort()  
    print  
    print "Source List:/t", l  
    l1,l2 = mean(l)  
    print "Result List:/t", l1, l2  
    print "Distance:/t", abs(sum(l1)-sum(l2))  
    print '-\*'\*40

输出结果  
Source List:    \[1, 2, 3, 4, 5, 6, 700, 800\]  
Result List:    \[1, 4, 5, 800\] \[2, 3, 6, 700\]  
Distance:       99  
\-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*

Source List:    \[1, 50, 90, 100, 10000, 10001\]  
Result List:    \[50, 90, 10000\] \[1, 100, 10001\]  
Distance:       38  
\-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*

Source List:    \[1, 2, 3, 4, 5, 6, 7, 8, 9, 10\]  
Result List:    \[2, 3, 6, 7, 10\] \[1, 4, 5, 8, 9\]  
Distance:       1  
\-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*-\*

Source List:    \[1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312\]  
Result List:    \[1, 3, 29, 232, 12311\] \[1, 2, 30, 210, 12312\]  
Distance:       21

**33.**实现一个挺高级的字符匹配算法：  
给一串很长字符串，要求找到符合要求的字符串，例如目的串：123  
1\*\*\*\*\*\*3\*\*\*2 ,12\*\*\*\*\*3这些都要找出来  
其实就是类似一些和谐系统。。。。。

分析：  
自然匹配就是对待匹配的每个字符挨个匹配  
设你的待匹配字串长度位n,模式字符串长度位m.  
对于待匹配字符串中的任意一个字符最坏情况下要匹配m次，也就是说这个字符不在模式字符串中。  
所以最坏情况下总共是m\*n此匹配，时间复杂度就是O(m\*n)

倘若使用hash表对待字符串进行hash处理O(n)的时间复杂度，那么对于模式字符串中的任意字符，  
仅需一次hash判断就可以得知是否在待匹配字符串中出现。  
最坏仅需m次就可以得到结果。时间复杂度为O(m)或者O(n);

与此题相类似：  
就是给一个很长的字符串str 还有一个字符集比如\{a,b,c\} 找出str里包含\{a,b,c\}的最短子串。  
要求O(n)?  
比如，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc。

用两个变量 front rear 指向一个的子串区间的头和尾  
用一个int cnt\[255\]=\{0\}记录当前这个子串里 字符集a,b,c 各自的个数，  
一个变量sum记录字符集里有多少个了

rear 一直加，更新cnt\[\]和sum的值，直到 sum等于字符集个数  
然后front++,直到cnt\[\]里某个字符个数为0，这样就找到一个符合条件的字串了

继续前面的操作，就可以找到最短的了。  
//还有没有人，对此题了解的比较深的? 望 也多阐述下...:)。

**34.实现一个队列。**  
队列的应用场景为：  
一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列

生产者消费者线程演示    
一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列

\#include <windows.h>     
\#include <stdio.h>     
\#include <process.h>     
\#include <iostream>     
\#include <queue>     
using namespace std;     
HANDLE ghSemaphore;   //信号量     
const int gMax = 100; //生产(消费)总数     
std::queue<int> q;      //生产入队,消费出队

//生产者线程     
unsigned int \_\_stdcall producerThread(void\* pParam)      
\{     
    int n = 0;     
    while(++n <= gMax)     
    \{     
        //生产     
        q.push(n);     
        cout<<"produce "<<n<<endl;     
        ReleaseSemaphore(ghSemaphore, 1, NULL); //增加信号量     
        Sleep(300);//生产间隔的时间,可以和消费间隔时间一起调节     
    \}     
    \_endthread(); //生产结束     
    return 0;     
\}   
    
//消费者线程  
unsigned int \_\_stdcall customerThread(void\* pParam)  
\{  
 int n = gMax;  
 while(n--)  
 \{  
  WaitForSingleObject(ghSemaphore, 10000);  
  //消费  
    
  q.pop();

cout<<"custom   "<<q.front()<<endl;   //小肥杨指出，原答案这句和上句搞错了顺序?  
  Sleep(500);//消费间隔的时间,可以和生产间隔时间一起调节  
 \}  
 //消费结束  
 CloseHandle(ghSemaphore);  
 cout<<"working end."<<endl;  
 \_endthread();  
 return 0;  
\}

void threadWorking()     
\{     
    ghSemaphore = CreateSemaphore(NULL, 0, gMax, NULL); //信号量来维护线程同步     
         
    cout<<"working start."<<endl;     
    unsigned threadID;     
    HANDLE handles\[2\];     
    handles\[0\] = (HANDLE)\_beginthreadex(      
                    NULL,      
                    0,      
                    producerThread,      
                    nullptr,      
                    0,      
                    &threadID);     
    handles\[1\] = (HANDLE)\_beginthreadex(      
                    NULL,      
                    0,      
                    customerThread,      
                    nullptr,      
                    0,      
                    &threadID);      
    WaitForMultipleObjects(2, handles, TRUE, INFINITE);     
\}    
   
int main()     
\{     
    threadWorking();     
    getchar();     
    return 0;     
\}

**35.**  
求一个矩阵中最大的二维矩阵(元素和最大).如:  
1 2 0 3 4  
2 3 4 5 1  
1 1 5 3 0  
中最大的是:  
4 5  
5 3  
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码  
此第35题与第3题相类似，一个是求最大子数组和，一个是求最大子矩阵和。

3.求子数组的最大和  
题目：  
输入一个整形数组，数组里有正数也有负数。  
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。  
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，

int maxSum(int\* a, int n)  
\{  
  int sum=0;  
  int b=0;

for(int i=0; i<n; i++)  
  \{  
    if(b<=0)           //此处修正下，把b<0改为 b<=0  
      b=a\[i\];  
    else  
      b+=a\[i\];  
    if(sum<b)  
      sum=b;  
  \}  
  return sum;  
\}

//  
解释下：  
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，  
那么最大的子数组为3, 10, -4, 7, 2，  
因此输出为该子数组的和18

所有的东西都在以下俩行，  
即：  
  b：0  1  -1  3  13   9  16  18  7     
sum：0  1   1  3  13  13  16  18  18

其实算法很简单，当前面的几个数，加起来后，b<0后，  
把b重新赋值，置为下一个元素，b=a\[i\]。  
当b>sum，则更新sum=b;  
若b<sum，则sum保持原值，不更新。:)。July、10/31。  
///

现在回到我们的最初的最大子矩阵的问题,  
 假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵，  
如下所示(ari表示a\[r\]\[i\],假设数组下标从1开始)：

| a11 …… a1i ……a1j ……a1n |  
  | a21 …… a2i ……a2j ……a2n |  
  .....

| ar1 …… ari ……arj ……arn |     第r行 . . .  
  ..........                            |    
                                  V  
  | ak1 …… aki ……akj ……akn |   第k行 . . .

.....  
  | an1 …… ani ……anj ……ann |

那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下：  
 (ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)  
 由此我们可以看出最后所求的就是此一维数组的最大子断和问题，  
到此我们已经将问题转化为上面的已经解决了的问题了。

ar1  
..  
ak1  
注，是竖直方向，相加

//有误之处，肯定指正。:)。  
   \#include <iostream>     
 2 using namespace std;     
 3      
 4 int \*\* a;     
 5 int \*\*sum;   
   
 6 int max\_array(int \*a,int n)     
 7 \{     
 8         int \*c = new int \[n\];     
 9         int i =0;     
10         c\[0\] = a\[0\];     
11         for(i=1;i<n;i++)     
12         \{     
13                 if(c\[i-1\]<0)     
14                         c\[i\] = a\[i\];     
15                 else    
16                         c\[i\] = c\[i-1\]+a\[i\];     
17         \}     
18         int max\_sum = -65536;     
19         for(i=0;i<n;i++)     
20                 if(c\[i\]>max\_sum)     
21                         max\_sum = c\[i\];     
22         delete \[\]c;     
23         return max\_sum;     
24      
25 \}

26 int max\_matrix(int n)     
27 \{     
28         int i =0;     
29         int j = 0;     
30         int max\_sum = -65535;     
31         int \* b = new int \[n\];     
32      
33         for(i=0;i<n;i++)     
34         \{     
35                 for(j=0;j<n;j++)     
36                         b\[j\]= 0;     
37                 for(j=i;j<n;j++)  
//把数组从第i行到第j行相加起来保存在b中，在加时，自底向上，首先计算行间隔(j-i)等于1的情况，  
//然后计算j-i等于 2的情况，一次类推,在小间隔的基础上一次累加，避免重复计算     
38                 \{     
39                         for(int k =0;k<=n;k++)     
40                                 b\[k\] += a\[j\]\[k\];     
41                         int sum = max\_array(b,n);     
42                         if(sum > max\_sum)     
3                                 max\_sum = sum;     
44                 \}     
45         \}     
46         delete \[\]b;     
47         return max\_sum;     
48 \}

49 int main()     
50 \{     
51         int n;     
52         cin >> n;     
53      
54         a = new int \*\[n\];     
55         sum = new int \*\[n\];     
56         int i =0;     
57         int j =0;     
58         for(i=0;i<n;i++)     
59         \{     
60                 sum\[i\] = new int\[n\];     
61                 a\[i\] = new int\[n\];     
62                 for(j=0;j<n;j++)     
63                 \{     
64                         cin>>a\[i\]\[j\];     
65                         sum\[i\]\[j\] =0 ;  
                           //sum\[r\]\[k\]表示起始和结尾横坐标分别为r,k时的最大子矩阵     
66                         //sum\[r\]\[k\] = max\{sum (a\[i\]\[j\]):r<=i<=k\}:0<=k<=n-1     
67                 \}     
68         \}     
69         /\*    
70         int b\[10\]=\{31,-41,59,26,-53,58,97,-93,-23,84\};    
71         cout << max\_array(b,10) << endl;    
72         \*/    
73         cout << max\_matrix(n);     
74 \}

我们再来分析下这段，代码，为了让你真正弄透它。:)。  
//July，11.14.  
求最大子矩阵，我们先按给的代码的思路来：  
1.求最大子矩阵，我们把矩阵中，每一竖直方向的排列，看做一个元素。  
所以，矩阵就转化成了我们熟悉的一维数组。

即以上矩阵，相当于：  
a\[1->n\]\[1\] a\[1->n\]\[2\] ... a\[1->n\]\[i\] .. a\[1->n\]\[j\] .. a\[1->n\]\[n\]    
1->n表示竖直方向，同一列的元素相加。

2.先把这第r行->k行的列的元素，分别相加。  
即这段代码：  
26 int max\_matrix(int n)     
27 \{     
28         int i =0;     
29         int j = 0;     
30         int max\_sum = -65535;     
31         int \* b = new int \[n\];     
32      
33         for(i=0;i<n;i++)     
34         \{     
35                 for(j=0;j<n;j++)     
36                         b\[j\]= 0;     
37                 for(j=i;j<n;j++)  
//把数组从第i行到第j行相加起来保存在b中，在加时，自底向上，  
//首先计算行间隔(j-i)等于1的情况，然后计算j-i等于 2的情况，  
//一次类推,在小间隔的基础上一次累加，避免重复计算     
38                 \{     
39                         for(int k =0;k<=n;k++)     
40                                 b\[k\] += a\[j\]\[k\];     
41                         int sum = max\_array(b,n);     
42                         if(sum > max\_sum)     
3                                 max\_sum = sum;     
44                 \}     
45         \}     
46         delete \[\]b;     
47         return max\_sum;     
48 \}

咱们，来稍微分析下，  
即，求这段矩阵的和  
i行 a\[i\]\[1\] a\[r\]\[2\] ... a\[r\]\[k\] .. a\[r\]\[n\]  
 | a\[i+1\]\[1\]    
...  
 v a\[j-1\]\[1\]  
j行 a\[j\]\[1\] a\[j\]\[2\] ... a\[j\]\[k\] .. a\[j\]\[n\]

for(i=0;i<n;i++)  //第i行  
 \{  
   for(j=0;j<n;j++)  //第j行  
     b\[j\]=0;         //先把b\[j\]初始化为 0  
   for(j=i;j<n;j++)  //第i行->第j行   固定行  
    \{  
      for(int k=0;k<=n;k++)   //从上而下，列元素相加  
         b\[k\] += a\[j\]\[k\];  
         //相加之后，调用上述的求和函数max\_array(b,n)即可。  
         int sum=max\_array(b,n);  
         if(sum>max\_sum)  
            max\_sum=sum;   //sum->b的结果  
     \}  
  \}  
  delete \[\]b;  
  return max\_sum;

至于求和max\_array(int\* a,int n)函数，

6 int max\_array(int \*a,int n)     
 7 \{     
 8         int \*c = new int \[n\];     
 9         int i =0;     
10         c\[0\] = a\[0\];     
11         for(i=1;i<n;i++)     
12         \{     
13                 if(c\[i-1\]<0)     
14                         c\[i\] = a\[i\];     
15                 else    
16                         c\[i\] = c\[i-1\]+a\[i\];     
17         \}     
18         int max\_sum = -65536;     
19         for(i=0;i<n;i++)     
20                 if(c\[i\]>max\_sum)     
21                         max\_sum = c\[i\];     
22         delete \[\]c;     
23         return max\_sum;     
24      
25 \}

代码，则与这个差不多：  
int maxSum(int\* a, int n)  
\{  
  int sum=0;  
  int b=0;

for(int i=0; i<n; i++)  
  \{  
    if(b<0)           //其实，此处b<0，亦可。无需b<=0.  
      b=a\[i\];  
    else  
      b+=a\[i\];  
    if(sum<b)  
      sum=b;  
  \}  
  return sum;  
\}

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，  
那么最大的子数组为3, 10, -4, 7, 2，  
因此输出为该子数组的和18

所有的东西都在以下俩行，  
即：  
  b：0  1  -1  3  13   9  16  18  7     
sum：0  1   1  3  13  13  16  18  18

最后，矩阵之和，在main函数里，调用这个函数cout << max\_matrix(n);输出即可。  
有误之处，欢迎指正。

另外，调换俩个for循环的顺序，是否更精准?  
for(i=0;i<n;i++)  //第i行  
 \{  
   for(j=0;j<n;j++)  //第j行  
      b\[j\]=0;         //先把b\[j\]初始化为 0  
   for(int k=0;k<=n;k++)   //固定一列，然后0列->k列—>n列，逐级+。  
    \{  
      for(j=i;j<n;j++)  //第i行->第j行->第n行+ +++   
       //调换俩个for循环的顺序，是否更精准?

b\[k\] += a\[j\]\[k\];  
         //相加之后，调用上述的求和函数max\_array(b,n)即可。  
       int sum=max\_array(b,n);  
      if(sum>max\_sum)  
      max\_sum=sum;   //sum->b的结果  
     \}  
  \}  
 delete \[\]b;  
 return max\_sum;

完。:)

**36.引用自网友：longzuo**  
谷歌笔试：  
n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，  
存储在一个二维数组w\[n\]\[n\]中，w\[i\]\[j\] 的值代表编号为i，j的队伍中更强的一支。

所以w\[i\]\[j\]=i 或者j，现在给出它们的出场顺序，并存储在数组order\[n\]中，  
比如order\[n\] = \{4,3,5,8,1......\}，那么第一轮比赛就是 4对3， 5对8。.......

胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，  
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名

编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result\[n\]，求出result。

\#include <stdio.h>     
\#include <list>     
\#include <iostream>

void raceResult(int\*\* w, int\* order, int\* result, int n)     
\{     
    std::list<int> winer;     
         
    int count = n;     
    while(n)     
    \{     
        winer.push\_front(order\[--n\]);     
    \}     
         
    int resultNum = count - 1;     
    int nFirst, nSecond;     
    int round = 1;     
    while(winer.size() > 1)     
    \{     
        //一轮开始     
        std::cout<<std::endl<<"round "<<round++<<std::endl;     
        std::list<int>::iterator it = winer.begin();     
        while (it != winer.end())     
        \{     
            nFirst = \*it;     
            if (++it == winer.end())     
            \{     
                //轮空     
                std::cout<<nFirst<<" rest this round"<<std::endl;     
            \}     
            else    
            \{     
                nSecond = \*it;     
                int nWiner = \*((int\*)w + count \* nFirst + nSecond);     
                if (nWiner  == nFirst)     
                \{     
                    it = winer.erase(it);     
                    result\[resultNum--\] = nSecond;     
                    std::cout<<nFirst<<" kick out "<<nSecond<<std::endl;     
                \}     
                else    
                \{     
                    it = winer.erase(--it);     
                    result\[resultNum--\] = nFirst;     
                    ++it;     
                    std::cout<<nSecond<<" kick out "<<nFirst<<std::endl;     
                \}     
            \}     
        \}     
    \}     
    if (winer.size() == 1)     
    \{     
        result\[0\] = winer.front();     
    \}     
    std::cout<<std::endl<<"final result: ";     
    int nPlace = 0;     
    while(nPlace < count)     
    \{     
        std::cout<<std::endl<<result\[nPlace++\];     
    \}     
\}

void test()     
\{     
    //team 2>team 1>team 3>team 0>team 4>team 5     
    int w\[6\]\[6\] = \{     
        0,1,2,3,0,0,     
        1,1,2,1,1,1,     
        2,2,2,2,2,2,     
        3,1,2,3,3,3,     
        0,1,2,3,4,5     
    \};     
    int order\[6\] = \{1,3,4,2,0,5\};     
    int result\[6\] = \{-1\};     
    raceResult((int\*\*)w, order, result, 6);     
    getchar();     
\}  
//自己加上主函数，测试了下，结果竟正确..

int main()  
\{  
    test();  
    return 0;  
\}

///

round 1  
1 kick out 3  
2 kick out 4  
0 kick out 5

round 2  
2 kick out 1  
0 rest this round

round 3  
2 kick out 0

final result:  
2  
0  
1  
5  
4  
3  
/

**37.**  
有n个长为m+1的字符串，  
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，  
问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

恩，好办法  
引用 5 楼 hblac 的回复:  
37. 把每个字符串看成一个图的顶点，两个字符串匹配就连一条有向边。相当于判断一个有向图  
是否有环以及求它的直径

38.百度面试：  
1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，  
使用x次天平，最多可以从y个小球中找出较轻的那个，求y与x的关系式

2.有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入  
流中随机取得m个记录  
3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度

38,1. y=3^x  
38,2. 每次输入一个记录时，随机产生一个0到1之间的随机数，  
用这些随机数维护一个大小为m的堆，即可。  
38,3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度  
这道题见过了，解法是构造一个hash函数，把url适当散列到若干个，  
比如1000个小文件中，然后在每个小文件中去除重复的url，再把他们合并。  
原理是相同的url，hash之后的散列值仍然是相同的。  
38,1  
samsho2  
我对天平称重这道题的理解是：  
每次将球分成三堆，尽可能让三堆球一样多或者让其中一堆多或者少一个。  
球数y和沉重次数x的关系是：  
y=1 =》x=0；（显然）  
y=2 =》x=1；（显然）  
y=3 =》x=2；（显然）  
如果y>3，也是将球分为三堆，记为A堆、B堆、C堆  
if y=3k（k>1）     
  称重一次，就可以判断瑕疵球在哪堆，从而使得球数降为k个；  
if y=3k+1（k>=1） 假设C堆多放1球，A堆和B堆进行称重     
  称重一次，就可以判断瑕疵球在哪堆，  
  if A == B ，瑕疵球在C堆，从而使得球数降为k+1个；  
  else 瑕疵球在轻的堆，从而使得球数降为k个；  
if y=3k-1（k>=2） 假设C堆少放1球，A堆和B堆进行称重     
  称重一次，就可以判断瑕疵球在哪堆，  
  if A == B ，瑕疵球在C堆，从而使得球数降为k个；  
  else 瑕疵球在轻的堆，从而使得球数降为k-1个；

利用以上过程反复，可得结果。  
最后的次数x = log3（y），可能在y哪里还需要做点什么修正。但复杂度就是log y

38，1.  
用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，  
使用x次天平 最多可以从y个小球中找出较轻的那个，求y与x的关系式

hengchun11  
 用天平比较二边放一样的球数：有三种可能性     
第一种 左边重 说明较轻的在右边；  
第二种 右边重 说明较轻的在左边；  
第三种 一样重 说明较轻的不在这里面；  
以上有三种可能性，在称x=1的情况下，说明 y=2是可以称出来的 y=3，也是可以的；y=4就不行

了  
所以 我觉得 分成三部分来称 就可以称出最多的球  
x=1 y=3  
x=2 y=9  
x=3 y=27  
可以得出y=3的x次方

39.  
网易有道笔试：  
(1).  
求一个二叉树中任意两个节点间的最大距离，  
两个节点的距离的定义是 这两个节点间边的个数，  
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。

(2).  
求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，  
有向图不再连通，描述算法。

先看第39题的第1小问，  
求一个二叉树中任意俩个结点之间的距离。  
以前自个，写的，求二叉树中节点的最大距离...

void traversal\_MaxLen(NODE\* pRoot)  
\{   
    if(pRoot == NULL)  
    \{  
        return 0;  
    \};  
      
    if(pRoot->pLeft == NULL)      
    \{  
        pRoot->MaxLeft = 0;  
    \}  
    else                                 //若左子树不为空  
    \{  
        int TempLen = 0;  
        if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight)  
          //左子树上的，某一节点，往左边大，还是往右边大  
        \{  
            TempLen+=pRoot->pLeft->MaxLeft;  
        \}  
        else  
        \{  
            TempLen+=pRoot->pLeft->MaxRight;  
        \}  
        pRoot->nMaxLeft = TempLen + 1;  
        traversal\_MaxLen(NODE\* pRoot->pLeft);   
        //此处，加上递归  
    \}  
      
    if(pRoot->pRigth == NULL)  
    \{  
        pRoot->MaxRight = 0;  
    \}  
    else                                //若右子树不为空  
    \{  
        int TempLen = 0;  
        if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight)    
        //右子树上的，某一节点，往左边大，还是往右边大  
        \{  
            TempLen+=pRoot->pRight->MaxLeft;  
        \}  
        else  
        \{  
            TempLen+=pRoot->pRight->MaxRight;  
        \}  
        pRoot->MaxRight = TempLen + 1;  
        traversal\_MaxLen(NODE\* pRoot->pRight);   
        //此处，加上递归  
    \}  
      
   if(pRoot->MaxLeft + pRoot->MaxRight > 0)  
    \{  
        MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;  
    \}  
\}

// 数据结构定义  
    struct NODE  
    \{  
         NODE\* pLeft;            // 左子树  
         NODE\* pRight;          // 右子树  
         int nMaxLeft;          // 左子树中的最长距离  
         int nMaxRight;         // 右子树中的最长距离  
         char chValue;        // 该节点的值  
    \};  
      
    int nMaxLen = 0;  
      
    // 寻找树中最长的两段距离  
    void FindMaxLen(NODE\* pRoot)  
    \{  
         // 遍历到叶子节点，返回  
         if(pRoot == NULL)  
         \{  
              return;  
         \}  
      
         // 如果左子树为空，那么该节点的左边最长距离为0  
         if(pRoot -> pLeft == NULL)  
         \{  
              pRoot -> nMaxLeft = 0;   
         \}  
      
         // 如果右子树为空，那么该节点的右边最长距离为0  
         if(pRoot -> pRight == NULL)  
         \{  
              pRoot -> nMaxRight = 0;  
         \}  
      
         // 如果左子树不为空，递归寻找左子树最长距离  
         if(pRoot -> pLeft != NULL)  
         \{  
              FindMaxLen(pRoot -> pLeft);  
         \}  
      
         // 如果右子树不为空，递归寻找右子树最长距离  
         if(pRoot -> pRight != NULL)  
         \{  
              FindMaxLen(pRoot -> pRight);  
         \}  
      
         // 计算左子树最长节点距离  
         if(pRoot -> pLeft != NULL)  
         \{  
              int nTempMax = 0;  
              if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)  
              \{  
                   nTempMax = pRoot -> pLeft -> nMaxLeft;  
              \}  
              else  
              \{  
                   nTempMax = pRoot -> pLeft -> nMaxRight;  
              \}  
              pRoot -> nMaxLeft = nTempMax + 1;  
         \}  
      
         // 计算右子树最长节点距离  
         if(pRoot -> pRight != NULL)  
         \{  
              int nTempMax = 0;  
              if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)  
              \{  
                   nTempMax = pRoot -> pRight -> nMaxLeft;  
              \}  
              else  
              \{  
                   nTempMax = pRoot -> pRight -> nMaxRight;  
              \}  
              pRoot -> nMaxRight = nTempMax + 1;  
         \}  
      
         // 更新最长距离  
         if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)  
         \{  
              nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;  
         \}  
\}  
//很明显，思路完全一样，但书上 给的这段代码 更规范！:)。

zhoulei0907  
/\*  
 \* return the depth of the tree  
 \*/  
int get\_depth(Tree \*tree) \{  
    int depth = 0;  
    if ( tree ) \{  
        int a = get\_depth(tree->left);  
        int b = get\_depth(tree->right);  
        depth = ( a > b ) ? a : b;  
        depth++;  
    \}  
    return depth;  
\}

/\*  
 \* return the max distance of the tree  
 \*/  
int get\_max\_distance(Tree \*tree) \{  
    int distance = 0;  
    if ( tree ) \{  
        // get the max distance connected to the current node  
        distance = get\_depth(tree->left) + get\_depth(tree->right);

// compare the value with it's sub trees  
        int l\_distance = get\_max\_distance(tree->left);  
        int r\_distance = get\_max\_distance(tree->right);  
        distance = ( l\_distance > distance ) ? l\_distance : distance;  
        distance = ( r\_distance > distance ) ? r\_distance : distance;  
    \}  
    return distance;  
\}

解释一下，get\_depth函数是求二叉树的深度，用的是递归算法：  
一棵二叉树的深度就是它的左子树的深度和右子树的深度，两者的最大值加一。

get\_max\_distance函数是求二叉树的最大距离，也是用递归算法：  
首先算出经过根节点的最大路径的距离，其实就是左右子树的深度和；  
然后分别算出左子树和右子树的最大距离，三者比较，最大值就是当前二叉树的最大距离了。

这个算法不是效率最高的，因为在计算二叉树的深度的时候存在重复计算。  
但应该是可读性比较好的，同时也没有改变原有二叉树的结构和使用额外的全局变量。

July：  
很好。那么，咱们再来 探讨下这个二叉树的最大距离问题。  
计算一个二叉树的最大距离有两个情况:  
  情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。  
  情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。  
只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。

简单的写下算法。  
1.如果根结点，为空，当然 return 0；  
2.如果左子树不为空，  
    寻找左子树上最深的那个点（左深度）。  
  否则，左子树为空  
    不寻找。  
    //即最大距离不通过根结点。  
    //即最大距离为maxLeft =左深度+1  
3.如果右子树不为空  
    寻找右子树上最深的那个点（右深度）。  
  否则，右子树为空  
    不寻找。  
    //即最大距离不通过根结点。  
    //即最大距离为maxRight =右深度+1  
所以，最大的距离，即为  
当有左，无右时，则最大距离maxLen=maxLeft（左深度）+1               //不过根结点  
当有右，无左时，则最大距离maxLen=maxRight（右深度）+1              //不过根结点  
当有左，也有右时，则最大距离maxLen=maxLeft（左深度）+1 + maxRight（右深度）+1   //过根结点

三者，比较，即得，最终的maxLen。

然后么最后的问题就只剩，求左子树maxLeft或者右子树maxRight的深度问题。  
求一个子树，如左子树的maxLeft，即深度问题，  
我们可以这么考虑，  
左子树不为空，左子树上的，某一节点，往左边大，还是往右边大  
往左边大，那么maxLen加上 往左边的距离，  即相当于搜索往深的那一边 左边 搜索  
往右边大，那么maxLen加上 往右边的距离。  即相当于搜索往深的那一边 左边 搜索

好比 凿井一样，总要往更深的方向凿。  
凿到某一个深度后，想下，是往左边一点凿，更好列，还是往右边一点点凿更好列。  
总之，目的就是为了，凿到更大 的深度。  
就是这个道理了。:)。

经过上述，我一番苦口婆心之后，再来看以下这段代码，是不是更加容易懂了。  
:)....

void FindMaxLen(NODE\* pRoot)  
    \{  
         // 遍历到叶子节点，返回  
         if(pRoot == NULL)  
         \{  
              return;  
         \}  
      
         // 如果左子树为空，那么该节点的左边最长距离为0  
         if(pRoot -> pLeft == NULL)  
         \{  
              pRoot -> nMaxLeft = 0;   
         \}  
      
         // 如果右子树为空，那么该节点的右边最长距离为0  
         if(pRoot -> pRight == NULL)  
         \{  
              pRoot -> nMaxRight = 0;  
         \}  
      
         // 如果左子树不为空，递归寻找左子树最长距离  
         if(pRoot -> pLeft != NULL)  
         \{  
              FindMaxLen(pRoot -> pLeft);  
         \}  
      
         // 如果右子树不为空，递归寻找右子树最长距离  
         if(pRoot -> pRight != NULL)  
         \{  
              FindMaxLen(pRoot -> pRight);  
         \}  
      
         // 计算左子树最长节点距离  
         if(pRoot -> pLeft != NULL)  
         \{  
              int nTempMax = 0;  
              if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)  
              \{  
                   nTempMax = pRoot -> pLeft -> nMaxLeft;  
              \}  
              else  
              \{  
                   nTempMax = pRoot -> pLeft -> nMaxRight;  
              \}  
              pRoot -> nMaxLeft = nTempMax + 1;  
         \}  
      
         // 计算右子树最长节点距离  
         if(pRoot -> pRight != NULL)  
         \{  
              int nTempMax = 0;  
              if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)  
              \{  
                   nTempMax = pRoot -> pRight -> nMaxLeft;  
              \}  
              else  
              \{  
                   nTempMax = pRoot -> pRight -> nMaxRight;  
              \}  
              pRoot -> nMaxRight = nTempMax + 1;  
         \}  
      
         // 更新最长距离  
         if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)  
         \{  
              nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;  
         \}  
\}

求左子树maxLeft或者右子树maxRight的深度问题，就涉及一个递归问题了。  
即我们搜索 这个树的深度时，不一直就用着递归往下搜索么。

好比凿井，当我们试探性的是往左，还是往右，更深一点，  
如果，能往右，那么递归 往右凿， //即只要右子树存在，那么不断的递归右子树，找最大深度。  
如果，能往左，那么递归 往左凿。 //即只要左子树存在，那么不断的递归左子树，找最大深度。  
这样，井是不是 已经凿 的很深了。  
很享受，这种凿井的过程，  
希望，我能与更多的人，一起来凿井，越凿越要往深处凿，凿的越深越好。

同时，把每一道题目，解释的越简单易懂，则是我的目标之一。  
谢谢。:)

**39.**  
网易有道笔试：  
(2).  
求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，  
有向图不再连通，描述算法。

网友回复，有误，指正：  
求无向连通图的割点集  
mysword  
最简单的，删掉一个点然后判断连通性，不就可以了？ //这句话，道出了割点的定义。  
BlueSky2008  
可以更简单一些：    
在深度优先树中，根结点为割点，当且仅当他有两个或两个以上的子树。    
其余结点v为割点，当且仅当存在一个v的后代结点s，s到v的祖先结点之间没有反向边。

记发现时刻dfn(v)为一个节点v在深度优先搜索过程中第一次遇到的时刻。    
记标号函数low(v) = min(dfn(v), low(s), dfn(w))    
s是v的儿子，(v,w)是反向边。

low(v) 表示从v或v的后代能追溯到的标号最小的节点。

则非根节点v是割点，当且仅当存在v的一个儿子s，low(s) > = dfn(v)  
40.百度研发笔试题  
引用自：zp155334877  
1)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。

2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，  
设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。  
并分析时间复杂度与空间复杂度。

3)设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，  
则中国人民 人民中国都有效。要求：

\*系统每秒的查询数量可能上千次；  
  \*词语的数量级为10W；  
  \*每个词至多可以与1W个词搭配

当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。

**40.百度研发笔试题**  
引用自：zp155334877  
1)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。……

所以，此题的第1小题，即是借助辅助栈，保存最小值，  
且随时更新辅助栈中的元素。  
如先后，push 2 6 4 1 5  
 stack A  stack B（辅助栈）

4:  5       1      //push 5,min=p->\[3\]=1     ^  
3:  1       1      //push 1,min=p->\[3\]=1     |  //此刻push进A的元素1小于B中栈顶元素2  
2:  4       2      //push 4,min=p->\[0\]=2     |  
1:  6       2      //push 6,min=p->\[0\]=2     |  
0:  2       2      //push 2,min=p->\[0\]=2     |

push第一个元素进A，也把它push进B，  
当向Apush的元素比B中的元素小，  则也push进B，即更新B。否则，不动B，保存原值。  
向栈A push元素时，顺序由下至上。  
辅助栈B中，始终保存着最小的元素。

然后，pop栈A中元素，5 1 4 6 2  
     A       B ->更新    
4:   5       1    1     //pop 5,min=p->\[3\]=1      |  
3:   1       1    2     //pop 1,min=p->\[3\]=2      |    //下文指的是这里错了。  
2:   4       2    2     //pop 4,min=p->\[0\]=2      |  
1:   6       2    2     //pop 6,min=p->\[0\]=2      |  
0:   2       2    NULL  //pop 2,min=p->\[0\]=NULL   v

当pop A中的元素小于B中栈顶元素时，则也要pop B中栈顶元素。

index 貌似错了，修正下，

所以，此题的第1小题，即是借助辅助栈，保存最小值，  
且随时更新辅助栈中的元素。  
如先后，push 2 6 4 1 5  
 stack A  stack B（辅助栈）

4:  5       1      //push 5,min=p->\[3\]=1     ^  
3:  1       1      //push 1,min=p->\[3\]=1     |   //此刻push进A的元素1小于B中栈顶元素2  
2:  4       2      //push 4,min=p->\[0\]=2     |  
1:  6       2      //push 6,min=p->\[0\]=2     |  
0:  2       2      //push 2,min=p->\[0\]=2     |

然后，pop栈A中元素，5 1 4 6 2  
     A       B ->更新    
4:   5       1    1     //pop 5,min=p->\[3\]=1      |  
3:   1       1    2     //pop 1,min=p->\[0\]=2      |  
2:   4       2    2     //pop 4,min=p->\[0\]=2      |  
1:   6       2    2     //pop 6,min=p->\[0\]=2      |  
0:   2       2    NULL  //pop 2,min=NULL          v

当pop A中的元素小于B中栈顶元素时，则也要pop B中栈顶元素。

2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，  
设计一个算法，取出其中一段……  
2.就是给一个很长的字符串str 还有一个字符集比如\{a,b,c\} 找出str里包含\{a,b,c\}的最短子串。  
要求O(n)?  
比如，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc

用两个变量 front，rear 指向一个的子串区间的头和尾  
用一个int cnt\[255\]=\{0\}记录当前这个子串里 字符集a,b,c 各自的个数，  
一个变量sum记录字符集里有多少个了。

rear 一直加，更新cnt\[\]和sum的值，直到 sum等于字符集个数  
然后front++,直到cnt\[\]里某个字符个数为0，这样就找到一个符合条件的字串了

继续前面的操作，就可以找到最短的了。  
3.  
可以建立一个RDF文件，利用protege 4.0。或者自己写的RDF/XML接口也行。  
在其中建立两个“描述对象”一个是国家，一个是人民。 国家之下建立一个中国，  
人民。并且在关系中建立一个关系：对每个存在的国家，都have人民。  
这样，每当用户输入这两个词的时候，  
就利用语义框架/接口来判断一下这两个词汇的关系，返回一个值即可。

\--贝叶斯分类--  
其实贝叶斯分类更实用一些。 可以用模式识别的贝叶斯算法，  
写一个类并且建立一个词汇-模式的表。  
这个表中每个模式，也就是每个词汇都设一个域，可以叫做most-fitted word，  
然后对这个分类器进行训练。

这个训练可以在初期设定一些关联词汇；也可以在用户每次正确输入查询的时候来训练。通过训练，每个单

词对应出现概率最高的单词设到最适合域里面。  
然后对于每个词，都返回最适合的单词。

作者声明：  
本人July 对以上公布的所有任何题目或资源享有版权。  
转载以上公布的任何一题，或资源，请注明出处，及作者我本人。  
向你的厚道致敬。谢谢。

July、2010年11月14日，晚，于东华理工。  
（答案V0.3版完）  
//完整答案V0.3版，请到我的资源下载处下载。

[http_topic.csdn.net_u_20101126_10_b4f12a00-6280-492f-b785-cb6835a63dc9.html]: http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html
[http_topic.csdn.net_u_20101126_10_b4f12a00-6280-492f-b785-cb6835a63dc9_8.html]: http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9_8.html