微软等面试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
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。有任何问题，欢迎任何朋友随时指出。二零一一年四月二十日，July，updated。// 21题递归方法 //这个，没有任何问题 //from yansha //July、updated。 #include<list> #include<iostream> using namespace std; list<int>list1; void find_factor(int sum, int n) { // 递归出口 if(n <= 0 || sum <= 0) return; // 输出找到的结果 if(sum == n) { // 反转list list1.reverse(); for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++) cout << *iter << " + "; cout << n << endl; list1.reverse(); } list1.push_front(n); //典型的01背包问题 find_factor(sum-n, n-1); //放n，n-1个数填满sum-n list1.pop_front(); find_factor(sum, n-1); //不放n，n-1个数填满sum } int main() { int sum, n; cout << "请输入你要等于多少的数值sum:" << endl; cin >> sum; cout << "请输入你要从1.....n数列中取值的n：" << endl; cin >> n; cout << "所有可能的序列，如下：" << endl; find_factor(sum,n); return 0; }
第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 Abb.rr bb.rr
2.B C Abb rr bb/RR/BR,=>A:BRrr bb =>A:BR
3.B C ABR BB RR/BR, =>A:BR//推出A:BR的原因，//如果 A是 RR，//那么，当ABC都说不知道后，B 最后应该知道自己是BR了。//因为B 不可能 是 RR或BB。
4.B C ABR 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 pEndvoid 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->ba2. cdef->fedc原字符串变为bafedc3. 整个翻转：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 defghidef abcghidef ghi abc //最后的 复杂度是O（m+n） 再举一个例子，如果123 4567890要变成4567890 123： 123 45678901. 456 123 78902. 456789 123 03. 456789 12 0 34. 456789 1 0 235. 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=1f(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.实现一个挺高级的字符匹配算法：给一串很长字符串，要求找到符合要求的字符串，例如目的串：1231******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 42 3 4 5 11 1 5 3 0中最大的是:4 55 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表示竖直方向，同一列的元素相加。
那么，假设最大子矩阵，是在第r行->第k行，所有元素的和。 | ar1 …… ari ……arj ……arn | | . . . . | | . . . . | | ak1 …… aki ……akj ……akn |所以题目就转化成了类似第3题的思路。
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 11 kick out 32 kick out 40 kick out 5
round 22 kick out 10 rest this round
round 32 kick out 0
final result:201543/
37.有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
恩，好办法引用 5 楼 hblac 的回复:37. 把每个字符串看成一个图的顶点，两个字符串匹配就连一条有向边。相当于判断一个有向图是否有环以及求它的直径
38.百度面试：1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，最多可以从y个小球中找出较轻的那个，求y与x的关系式
2.有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中随机取得m个记录3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度
38,1. y=3^x38,2. 每次输入一个记录时，随机产生一个0到1之间的随机数，用这些随机数维护一个大小为m的堆，即可。38,3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度这道题见过了，解法是构造一个hash函数，把url适当散列到若干个，比如1000个小文件中，然后在每个小文件中去除重复的url，再把他们合并。原理是相同的url，hash之后的散列值仍然是相同的。38,1samsho2我对天平称重这道题的理解是：每次将球分成三堆，尽可能让三堆球一样多或者让其中一堆多或者少一个。球数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=3x=2 y=9x=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 =左深度+13.如果右子树不为空 寻找右子树上最深的那个点（右深度）。 否则，右子树为空 不寻找。 //即最大距离不通过根结点。 //即最大距离为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.百度研发笔试题引用自：zp1553348771)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。
2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。
3)设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，则中国人民 人民中国都有效。要求：
*系统每秒的查询数量可能上千次； *词语的数量级为10W； *每个词至多可以与1W个词搭配
当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。
40.百度研发笔试题引用自：zp1553348771)设计一个栈结构，满足一下条件：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中栈顶元素22: 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中栈顶元素22: 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->[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版，请到我的资源下载处下载。----------------------------------------
作者声明：本人July对本博客所有文章和资料享有版权，转载或引用任何文章、资料请注明出处。谢谢。 July、二零一一年一月十日。
