【正文】 ANSWERHave done this.(2).求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。，大到?jīng)]有存儲(chǔ)器可以將其存儲(chǔ)下來，而且只輸入一次，如何從這個(gè)輸入流中隨機(jī)取得m 個(gè)記錄。}Time plexity analysis:Hash calculation: O(nm)Graph construction: O(n*n)Toplogical sort: as dfs, O(V+E)All source longest path: O(kE), k is 0indegree vetexes number, E is edge number.As a total, it’s a O(n*n+n*m) solution.A very good problem. But I really doubt it as a solvein20min interview question.38.百度面試：（只能比較，不能稱重）從一堆小球中找出其中唯一一個(gè)較輕的，使用x 次天平，最多可以從y 個(gè)小球中找出較輕的那個(gè)，求y 與x 的關(guān)系式。top[t++] = s。dfs(graph, graph[s][i])。 //gray node, a back edge。amp。 i=graph[s][0]。}int topdfs(int graph[], int s) {if (visited[s] != 0) return 1。 i++) {if (topdfs(graph, i) == 0) return 0。for (int i=0。int topSort(int graph[]){memset(visit, 0, n*sizeof(int))。int finished[MAX_NUM]。} }}}return min。parent[graph[top[j]][k]] = top[j]。 k=graph[top[j]][0]。 jn。d[i] = 0。memset(parent, 1, n*sizeof(int))。 in。 //topological sort failed, there is cycle.int min = 0。int longestPath(int graph[], int n) {memset(visit, 0, n*sizeof(int))。int parent[MAX_NUM]。} }}return longestPath(graph, n)。graph[i][graph[i*n]] = j。 strncmp(strs[i]+1, strs[j], m) == 0) {if (i==j) return 0。 j++) {if (suffixHash[i]==prefixHash[j] amp。 i++) {for (j=0。for (i=0。graph[i][0] = 0。 in。 int i,j。int prefixHash[MAX_NUM]。ANSWERThis is identical to the problem to find the longest acylic path in a directed graph. If there is a cycle, return false.Firstly, build the graph. Then search the graph for the longest path.define MAX_NUM 201int inDegree[MAX_NUM]。j++。 i+=2) {int win= (i==round1) ? i : w[i][i+1]。for (i=0,j=0。memcpy(result, order, n*sizeof(int))。.......勝者晉級(jí)，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分，即可以隨便排，下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4 對(duì)5,直至出現(xiàn)第一名編程實(shí)現(xiàn)，給出二維數(shù)組w，一維數(shù)組order 和用于輸出比賽名次的數(shù)組result[n]，求出result。n1，已知它們之間的實(shí)力對(duì)比關(guān)系，存儲(chǔ)在一個(gè)二維數(shù)組w[n][n]中，w[i][j] 的值代表編號(hào)為i，j 的隊(duì)伍中更強(qiáng)的一支。 j++) {acc[i*n+j] = acc[j] acc[i1]。 i++) {for (j=i。}for (i=1。in。acc[i] = a[i]。(2)分析時(shí)間復(fù)雜度。ANSWERNot a clear problem. Seems a bitset can do.34.實(shí)現(xiàn)一個(gè)隊(duì)列。ANSWERIf only one swap can be taken, it is a O(n^2) searching problem, which can be reduced to O(nlogn) by sorting the arrays and doing binary search.If any times of swaps can be performed, this is a double binatorial problem.In the book beauty of codes, a similar problem splits an array to halves as even as possible. It is possible to take binary search, when SUM of the array is not too high. Else this is a quite time consuming brute force problem. I cannot figure out a reasonable solution.33.實(shí)現(xiàn)一個(gè)挺高級(jí)的字符匹配算法：給一串很長字符串，要求找到符合要求的字符串，例如目的串：1231******3***2 ,12*****3 這些都要找出來其實(shí)就是類似一些和諧系統(tǒng)。例如:var a=[100,99,98,1,2, 3]。}return count。else count += prefix+base。 j++) {if (digit[j] 1) count += prefix。for (int j=0。}int count = 0。prefix[i] = (n suffix[i] digit[i]*base)/10。while (base n) {suffix[i] = n % base。 //10 is enough for 32bit integersint i=0。ANSWERThis is plicated... I hate it...Suppose we have N=ABCDEFG.if G1, of 1’s in the units digits is ABCDEF, else ABCDEF+1if F1, of 1’s in the digit of tens is (ABCDE)*10, else if F==1: (ABCDE)*10+G+1, else (ABCDE+1)*10if E1, of 1’s in 3rd digit is (ABCD)*100, else if E==1: (ABCD)*100+FG+1, else (ABCD+1)*100… so on.if A=1, of 1 in this digit is BCDEFG+1, else it’s 1*1000000。例如輸入12，從1 到12 這些整數(shù)中包含1 的數(shù)字有1，10，11 和12，1 一共出現(xiàn)了5 次。}}return 1。 () == pop[i2]) {()。while (!() amp。while (i2 n) {while (() || () != pop[i2])if (i1n) (push[i1++])。ANSWERThis seems interesting. However, a quite straightforward and promising way is to actually build the stack and check whether the pop action can be achieved.int isPopSeries(int push[], int pop[], int n) {stackint helper。因?yàn)榭梢杂腥缦碌膒ush 和pop 序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，這樣得到的pop 序列就是1。為了簡(jiǎn)單起見，我們假設(shè)push 序列的任意兩個(gè)整數(shù)都是不相等的。}、pop 序列題目：輸入兩個(gè)整數(shù)序列。n = 8。 }while (n!=0) {c+=tab[namp。 n = n amp。int countOf1(int n) {int c = 0。}return c。 (n1)。 (xxxxxx100001) = xxxxxx00000Note: for negative numbers, this also hold, even with 100000000 where the “1” leading to an underflow.int countOf1(int n) {int c=0。包括微軟在內(nèi)的很多公司都曾采用過這道題。例如輸入10，由于其二進(jìn)制表示為1010，有兩個(gè)1，因此輸出2。ANSWERf(n)=f(n1)+f(n2), f(1)=1, f(2)=2, let f(0) = 1, then f(n) = fibo(n1)。求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。要求時(shí)間對(duì)長度為n 的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。如把字符串a(chǎn)bcdef 左旋轉(zhuǎn)2 位得到字符串cdefab。return max。 i++)*outputstr++ = pstart++。}for (int i=0。len = 0。 *inputstr =’9’) {len ++。while (1) {if (*inputstr = ‘0’ amp。char * pstart = NULL。}第25 題：寫一個(gè)函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)功能：在字符串中找出連續(xù)最長的數(shù)字串，并把這個(gè)串的長度返回，并把這個(gè)最長數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr 所指內(nèi)存。} }currentnext = NULL。 h1=h1next。 current = currentnext。 h1datah2data)) {currentnext = h2。 h2 != NULL) {if (h1 == NULL || (h2!=NULL amp。while (h1 != NULL amp。 h1=h1next。 h2=h2next。Node * head。1:(*.*, , *.*)2:(*.*, , *.*)3:(*.*, , *.*)4:(*.*, , *.*)ANSWERCrap... I totally cannot understand this problem... Does the *.* represent any possible number?第24 題：鏈表操作，（1）.單鏈表就地逆置，（2）合并鏈表ANSWERReversing a linked list. Already done.What do you mean by merge? Are the original lists sorted and need to be kept sorted? If not, are there any special requirements?I will only do the sorted merging.Node * merge(Node * h1, Node * h2) {if (h1 == NULL) return h2。如果用程序，又怎么實(shí)現(xiàn)呢？ANSWERI dont’ like brain teaser. As an AI problem, it seems impossible to write the solution in 20 min...It seems that a bruteforce edge cutting strategy could do. Enumerate all possibilities, then for each guy delete the permutation that could be reduced if failed (for A, B, C at 1st round), Then there should be only one or one group of choices left.But who uses this as an interview question?第23 題：用最簡(jiǎn)單，最快速的方法計(jì)算出下面這個(gè)圓形是否和正方形相交。}PS: this is not an elegant imp