【正文】 lementation, however, it is not necessary to use gray code or other techniques for such a problem, right?第22 題：有4 張紅色的牌和4 張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C 三人額頭上貼任意兩張牌，A、B、C 三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A 說不知道，B 說不知道，C 說不知道，然后A 說知道了。 i++) if (aux[i]) printf(“%3d”, i+1)。}void dump(int aux[], int n) {for (int i=0。helper(destidx1, idx+1, aux, n)。helper(dest, idx+1, aux, n)。}void helper(int dest, int idx, int aux[], int n) {if (dest == 0) dump(aux, n)。memset(aux, 0, n*sizeof(int))。}PS: I didn’t figure out how to tell a overflow problem easily.第21 題2010 年中興面試題編程求解：輸入兩個整數(shù)n 和m，從數(shù)列1，2，3.......n 中隨意取幾個數(shù),使其和等于m ,要求將其中所有的可能組合列出來.ANSWERThis is a bination generation problem. void findCombination(int n, int m) {if (nm) findCombination(m, m)。}p++。 *p = 9) {num = num * 10 + (*p’0’)。while (*p != ‘\0’) {if (*p=0 amp。} else if (*p == ‘+’) {p++。if (*p == ‘’) {p++。ANSWER:This question checks how the interviewee is familiar with C/C++? I’m so bad at C/C++...int atoi(char * str) {int neg = 0。}}第20 題：題目：輸入一個表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。 1 == 1) {multiply(tmp, A, _r)。multiply(_r, _r, tmp)。 }int tmp[4]。}void power(int[] A, int n, int _r) {if (n==1) { memcpy(A, _r, 4*sizeof(int))。_r[2] = A[2]*B[0] + A[3]*B[2]。}void multiply(int[] A, int[] B, int _r) {_r[0] = A[0]*B[0] + A[1]*B[2]。power(A, n, result)。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}。分析：在很多C 語言教科書中講到遞歸函數(shù)的時候，都會用Fibonacci 作為例子。}hu...長出一口氣。 i++) {fn = (fn+m)%i。for (int i=2。ANSWER:Actually, although this is a so traditional problem, I was always to lazy to think about this or even to search for the answer.(What a shame...). Finally, by google I found the elegant solution for it.The keys are:1) if we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n2) after the first round, we start from k+1 ( possibly % n) with n1 elements, that is equal to an (n1) problem while start from (k+1)th element instead of 0, so the answer is (f(n1, m)+k+1)%n3) k = m1, so f(n,m)=(f(n1,m)+m)%n. finally, f(1, m) = 0。求出在這個圓圈中剩下的最后一個數(shù)字。 // this must the one that occurs exact 1 time.}第18 題：題目：n 個數(shù)字（0,1,…,n1）形成一個圓圈，從數(shù)字0 開始，每次從這個圓圈中刪除第m 個數(shù)字（第一個為當(dāng)前數(shù)字本身，第二個為當(dāng)前數(shù)字的下一個數(shù)字）。while (*p!=’\0’) {if (a[*p] == 1) return *p。p++。char *p=str。ANSWER:Again, this depends on what is “char”. Let’s assume it as ASCII.char firstSingle(char * str) {int a[255]。如輸入abaccdeff，則輸出b。if (()!=null) (())。} else {(n)。if (n==sentinel) {(“\n”)。 (sentinel)。LinkedListNode q=new LinkedListNode()。例如輸入78/ \6 10/ \ / \5 7 9 11輸出8 6 10 5 7 9 11。if (rootright != NULL) (rootright)。(rootright))。swap(amp。(root)。}void mirrorIteratively(Node * root) {if (root == NULL) return。mirror(rootleft)。(rootleft), amp。}void mirror(Node * root) {if (root == NULL) return。*l = *r。 // right child of node}。 // value of nodeBSTreeNode *m_pLeft。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。}if (sum == dest) printf(“%d, %d\n”, *f, *e)。 f e) {if (sum dest) sum = *(++f)。while (sum != dest amp。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。例如輸入數(shù)組115 和數(shù)字15。要求時間復(fù)雜度是O(n)。}return p。else return NULL。k0。Node *p=head, *pk=head。}。鏈表結(jié)點(diǎn)定義如下：struct ListNode{int m_nKey。}第13 題：題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k 個結(jié)點(diǎn)。 … T(r, n, 31)。 T(r, n,1)。 X+=(Yi)int foo(int n){int r=n。 (1i)) amp。}第12 題題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等關(guān)鍵字以及條件判斷語句（A?B:C）。depth = max(ld, rd)+1。int maxleft = helper(rootleft, ld)。 return 0。}int helper(Node * root, int amp。ANSWER:This is interesting... Also recursively, the longest distance between two nodes must be either from root to one leaf, or between two leafs. For the former case, it’s the tree height. For the latter case, it should be the sum of the heights of left and right subtrees of the two leaves’ most least ancestor.The first case is also the sum the heights of subtrees, just the height + 0.int maxDistance(Node * root) {int depth。Answer:Already done this. Skipped.第11 題求二叉樹中節(jié)點(diǎn)的最大距離...如果我們把二叉樹看成一個圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，我們姑且定義距離為兩節(jié)點(diǎn)之間邊的個數(shù)。為簡單起見，標(biāo)點(diǎn)符號和普通字母一樣處理。題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。return helper(a, s, l)。amp。int k = l。 i=s) i。while (a[e]a[i] amp。}int helper(int a[], int s, int e) {if (e==s) return 1。如果輸入5，沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回false。如果是返回true，否則返回false。(n3)n?，F(xiàn)在用同樣的方法增加7 倍。}return k。 i=1000。如果你在運(yùn)算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?ANSWER:Sum up all the numbers, then subtract the sum from 1001*1002/2.Another way, use A XOR A XOR B = B: int findX(int a[]) {int k = a[0]。此外，除一個數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。return (*p1 *p2)。if (*p1 == ‘\0’) return 1。amp。 *p1 == *p2) {p1++, p2++。 *p2 != ‘\0’ amp。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。}return 1。 strncmp(sub, plen+1, len) == 0) return ilen。 i=len amp。if (hash == dest amp。while (*p != ‘\0’) {if (i++len) hash = HBASE * dest + (int)(*p)。p = str。len ++。while (*p!=’\0’) {dest = HBASE * dest + (int)(*p)。int len = 0。}}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。if (i+1n)i+=aux[str[i+1]]。 str[j] == sub[k])。while (k=0 amp。i=len1。 i++) {aux[sub[i]] = len i。for (i=0。int aux[256]。ANSWER:KMP? BM? Sunday? Using BM or sunday, if it’s ASCII string, then it’s easy to fast access