【正文】 * merge(Node * h1, Node * h2) {if (h1 == NULL) return h2。}PS: this is not an elegant implementation, however, it is not necessary to use gray code or other techniques for such a problem, right?第22 題：有4 張紅色的牌和4 張藍色的牌，主持人先拿任意兩張，再分別在A、B、C 三人額頭上貼任意兩張牌，A、B、C 三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A 說不知道，B 說不知道，C 說不知道，然后A 說知道了。}void dump(int aux[], int n) {for (int i=0。helper(dest, idx+1, aux, n)。memset(aux, 0, n*sizeof(int))。}p++。while (*p != ‘\0’) {if (*p=0 amp。if (*p == ‘’) {p++。}}第20 題：題目：輸入一個表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。multiply(_r, _r, tmp)。}void power(int[] A, int n, int _r) {if (n==1) { memcpy(A, _r, 4*sizeof(int))。}void multiply(int[] A, int[] B, int _r) {_r[0] = A[0]*B[0] + A[1]*B[2]。ANSWER:This is the traditional problem of application of mathematics...let A={1 1}{1 0}f(n) = A^(n1)[0,0]this gives a O(log n) solution.int f(int n) {int A[4] = {1,1,1,0}。}hu...長出一口氣。for (int i=2。求出在這個圓圈中剩下的最后一個數(shù)字。while (*p!=’\0’) {if (a[*p] == 1) return *p。char *p=str。如輸入abaccdeff，則輸出b。} else {(n)。 (sentinel)。例如輸入78/ \6 10/ \ / \5 7 9 11輸出8 6 10 5 7 9 11。(rootright))。(root)。mirror(rootleft)。}void mirror(Node * root) {if (root == NULL) return。 // right child of node}。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。 f e) {if (sum dest) sum = *(++f)。ANSWER:Use two cursors. One at front and the other at the end. Keep track of the sum by moving the cursors.void find2Number(int a[], int n, int dest) {int *f = a, *e=a+n1。要求時間復(fù)雜度是O(n)。else return NULL。Node *p=head, *pk=head。鏈表結(jié)點定義如下：struct ListNode{int m_nKey。 … T(r, n, 31)。 X+=(Yi)int foo(int n){int r=n。}第12 題題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等關(guān)鍵字以及條件判斷語句（A?B:C）。int maxleft = helper(rootleft, ld)。}int helper(Node * root, int amp。Answer:Already done this. Skipped.第11 題求二叉樹中節(jié)點的最大距離...如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，我們姑且定義距離為兩節(jié)點之間邊的個數(shù)。題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。amp。 i=s) i。}int helper(int a[], int s, int e) {if (e==s) return 1。如果是返回true，否則返回false?，F(xiàn)在用同樣的方法增加7 倍。 i=1000。此外，除一個數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。if (*p1 == ‘\0’) return 1。 *p1 == *p2) {p1++, p2++。ANSWER:What is “paring two strings”? Just normal string parison? The natural way use O(n) time and O(1) space.int strcmp(char * p1, char * p2) {while (*p1 != ‘\0’ amp。 strncmp(sub, plen+1, len) == 0) return ilen。if (hash == dest amp。p = str。while (*p!=’\0’) {dest = HBASE * dest + (int)(*p)。}}However, this algorithm, as well as BM, KMP algorithms use O(|sub|) space. If this is not acceptable, Rabincarp algorithm can do it. Using hashing to fast filter out most false matchings.define HBASE 127int rc_strstr(char * str, char * sub) {int dest= 0。 str[j] == sub[k])。i=len1。for (i=0。ANSWER:KMP? BM? Sunday? Using BM or sunday, if it’s ASCII string, then it’s easy to fast access the auxiliary array. Otherwise an hashmap or bst may be needed. Lets assume it’s an ASCII string.int bm_strstr(char *str, char *sub) {int len = strlen(sub)。reverseFixlen(str, pstr)。str = p。char * p = str。 *p=c。void reverse(char *str) {reverseFixlen(str, strlen(str))。}return 0。} while (*str != ‘\0’)。ANSWER:I don’t understand what is “Chuanyue”.★用一種算法整理一個數(shù)組。p = pnext。Node * p = head。headnextnext = head。現(xiàn)在在不用遞歸式的情況下做一遍。有什么辦法呢？ANSWER: Skip.，你要用一根金條作為報酬。}第8 題此貼選一些比較怪的題，由于其中題目本身與算法關(guān)系不大，僅考考思維。 p2next!=NULL) {p1 = p1next。if (p==cylic1) return 0。Node *p = cylic1。amp。}// if there could exist cycleint isJoined(Node *h1, Node * h2) {Node* cylic1 = testCylic(h1)。}。上排的十個數(shù)如下：【0，1，2，3，4，5，6，7，8，9】舉一個例子，數(shù)值: 0,1,2,3,4,5,6,7,8,9分配: 6,2,1,0,0,0,1,0,0,00 在下排出現(xiàn)了6 次，1 在下排出現(xiàn)了2 次，2 在下排出現(xiàn)了1 次，3 在下排出現(xiàn)了0 次....以此類推..ANSWER:I don’t like brain teasers. Will skip most of them...第7 題微軟亞院之編程判斷倆個鏈表是否相交給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。 a[l+1] a[l]) l++。i = p。if (jn amp。例如輸入1，2，3，4，5，6，7 和8 這8 個數(shù)字，則最小的4 個數(shù)字為1，2，3 和4。if (rootright!=NULL) helper(rootright, sum, path, top)。if (rootleft == NULL amp。void printPaths(TreeNode * root, int sum) {int path[MAX_HEIGHT]。ANSWER:Use backtracking and recurison. We need a stack to help backtracking the path.struct TreeNode {int data。二元樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：struct BinaryTreeNode // a node in the binary tree{int m_nValue。}題目：輸入一個整數(shù)和一棵二元樹。while (cur size) {sum += a[cur++]。ANSWER: A traditional greedy approach.Keep current sum, slide from left to right, when sum 0, reset sum to 0.int maxSubarray(int a[], int size) {if (size=0) error(“error array size”)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。return [].data。pmin = (==0?d : [top1])。}void MinStackFree(MinStack stack) {free()。 = maxSize。struct MinStack {MinStackElement * data。要求函數(shù)min、push 以及pop 的時間復(fù)雜度都是O(1)。rhm_pLeft = root。if (lt!=NULL) {ltm_pRight = root。if (root == NULL) {head = NULL, tail = NULL。return head。 // left child of nodeBSTreeNode *m_pRight。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。我能夠看到此文，還要多謝陳同學(xué)！讓我得以及時分享給大家微軟面試100題全部答案個人整理的前60題的答案可參見以下三篇文章：1. 微軟100題第1題20題答案 [博文 I] 2. 微軟100題第2140題答案 [博文II] 3. 微軟100題第4160題答案 [博文III]最新整理的全部100題的答案參見如下（重復(fù)的，以及一些無關(guān)緊要的題目跳過）：題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。 // value of nodeBSTreeNode *m_pLeft。helper(head, tail, root)。 tail, BSTreeNode *root) {BSTreeNode *lt, *rh。helper(rh, tail, rootm_pRight)。}if (rh!=NULL) {rootm_pRight=rh。定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min 函數(shù)，能夠得到棧的最小元素。}。}MinStack MinStackInit(int maxSize) {MinStack stack。return stack。pdata = d。}int MinStackPop(MinStack stack) {if ( == 0) error(“stack is empty!”)。}題目：輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。例如輸入的數(shù)組為1, 2, 3, 10, 4, 7, 2, 5，和最大的子數(shù)組為3, 10, 4, 7, 2，因此輸出為該子數(shù)組的和18。int cur = 0。}}return max。例如輸入整數(shù)22 和如下二元樹10/ \5 12/ \4 7則打印出兩條路徑：10, 12 和10, 5, 7。 // right child of node}。}。sum = 。} else {if (rootleft != NULL) helper(rootleft, sum, path, top)。} 個