算法大全-數(shù)據(jù)結(jié)構(gòu) -面試題.doc

常用的等式：-n = (n-1) = n+1 獲取整數(shù)n的二進(jìn)制中最后一個(gè)1：n&(-n) 或者 n&(n-1)，如：n=010100，則-n=101100， n&(-n)=000100 去掉整數(shù)n的二進(jìn)制中最后一個(gè)1：n&(n-1)，如：n=010100，n-1=010011，n&(n-1)=010000 （PS：常用于檢查一個(gè)數(shù)的二進(jìn)制中有多少個(gè)1，我記得小米面試的時(shí)候考過我，我當(dāng)時(shí)沒用位運(yùn)算，顯得很笨很蠢哈，要考慮很多情況，希望有看到這個(gè)博客的朋友再去小米，直接秒殺之）。一、單鏈表目錄1.單鏈表反轉(zhuǎn)2.找出單鏈表的倒數(shù)第4個(gè)元素3.找出單鏈表的中間元素4.刪除無頭單鏈表的一個(gè)節(jié)點(diǎn)5.兩個(gè)不交叉的有序鏈表的合并6.有個(gè)二級單鏈表，其中每個(gè)元素都含有一個(gè)指向一個(gè)單鏈表的指針。寫程序把這個(gè)二級鏈表稱一級單鏈表。7.單鏈表交換任意兩個(gè)元素（不包括表頭）8.判斷單鏈表是否有環(huán)？如何找到環(huán)的“起始”點(diǎn)？如何知道環(huán)的長度？9.判斷兩個(gè)單鏈表是否相交10.兩個(gè)單鏈表相交，計(jì)算相交點(diǎn)11.用鏈表模擬大整數(shù)加法運(yùn)算12.單鏈表排序13.刪除單鏈表中重復(fù)的元素首先寫一個(gè)單鏈表的C#實(shí)現(xiàn)，這是我們的基石：public class Link public Link Next; public string Data; public Link(Link next, string data) this.Next = next; this.Data = data; 其中，我們需要人為地在單鏈表前面加一個(gè)空節(jié)點(diǎn)，稱其為head。例如，一個(gè)單鏈表是1-2-5，如圖所示：對一個(gè)單鏈表的遍歷如下所示：static void Main(string args) Link head = GenerateLink();Link curr = head;while (curr != null) Console.WriteLine(curr.Data); curr = curr.Next; 1.單鏈表反轉(zhuǎn)這道題目有兩種算法，既然是要反轉(zhuǎn)，那么肯定是要破壞原有的數(shù)據(jù)結(jié)構(gòu)的：算法1：我們需要額外的兩個(gè)變量來存儲當(dāng)前節(jié)點(diǎn)curr的下一個(gè)節(jié)點(diǎn)next、再下一個(gè)節(jié)點(diǎn)nextnext：public static Link ReverseLink1(Link head) Link curr = head.Next; Link next = null; Link nextnext = null; /if no elements or only one element exists if (curr = null | curr.Next = null) return head; /if more than one element while (curr.Next != null) next = curr.Next; /1 nextnext = next.Next; /2 next.Next = head.Next; /3 head.Next = next; /4 curr.Next = nextnext; /5 return head;算法的核心是while循環(huán)中的5句話我們發(fā)現(xiàn)，curr始終指向第1個(gè)元素。此外，出于編程的嚴(yán)謹(jǐn)性，還要考慮2種極特殊的情況：沒有元素的單鏈表，以及只有一個(gè)元素的單鏈表，都是不需要反轉(zhuǎn)的。算法2：自然是遞歸如果題目簡化為逆序輸出這個(gè)單鏈表，那么遞歸是很簡單的，在遞歸函數(shù)之后輸出當(dāng)前元素，這樣能確保輸出第N個(gè)元素語句永遠(yuǎn)在第N+1個(gè)遞歸函數(shù)之后執(zhí)行，也就是說第N個(gè)元素永遠(yuǎn)在第N+1個(gè)元素之后輸出，最終我們先輸出最后一個(gè)元素，然后是倒數(shù)第2個(gè)、倒數(shù)第3個(gè)，直到輸出第1個(gè)：public static void ReverseLink2(Link head) if (head.Next != null) ReverseLink2(head.Next); Console.WriteLine(head.Next.Data); 但是，現(xiàn)實(shí)應(yīng)用中往往不是要求我們逆序輸出（不損壞原有的單鏈表），而是把這個(gè)單鏈表逆序（破壞型）。這就要求我們在遞歸的時(shí)候，還要處理遞歸后的邏輯。首先，要把判斷單鏈表有0或1個(gè)元素這部分邏輯獨(dú)立出來，而不需要在遞歸中每次都比較一次：public static Link ReverseLink3(Link head) /if no elements or only one element exists if (head.Next = null | head.Next.Next = null) return head; head.Next = ReverseLink(head.Next); return head;我們觀測到：head.Next = ReverseLink(head.Next);這句話的意思是為ReverseLink方法生成的逆序鏈表添加一個(gè)空表頭。接下來就是遞歸的核心算法ReverseLink了：static Link ReverseLink(Link head) if (head.Next = null) return head; Link rHead = ReverseLink(head.Next); head.Next.Next = head; head.Next = null; return rHead;算法的關(guān)鍵就在于遞歸后的兩條語句：head.Next.Next = head; /1head.Next = null; /2啥意思呢？畫個(gè)圖表示就是：這樣，就得到了一個(gè)逆序的單鏈表，我們只用到了1個(gè)額外的變量rHead。2.找出單鏈表的倒數(shù)第4個(gè)元素這道題目有兩種算法，但無論哪種算法，都要考慮單鏈表少于4個(gè)元素的情況：第1種算法，建立兩個(gè)指針，第一個(gè)先走4步，然后第2個(gè)指針也開始走，兩個(gè)指針步伐（前進(jìn)速度）一致。static Link GetLast4thOne(Link head) Link first = head; Link second = head; for (int i = 0; i 4; i+) if (first.Next = null) throw new Exception(Less than 4 elements); first = first.Next; while (first != null) first = first.Next; second = second.Next; return second;第2種算法，做一個(gè)數(shù)組arr4，讓我們遍歷單鏈表，把第0個(gè)、第4個(gè)、第8個(gè)第4N個(gè)扔到arr0，把第1個(gè)、第5個(gè)、第9個(gè)第4N+1個(gè)扔到arr1，把第2個(gè)、第6個(gè)、第10個(gè)第4N+2個(gè)扔到arr2，把第3個(gè)、第7個(gè)、第11個(gè)第4N+3個(gè)扔到arr3，這樣隨著單鏈表的遍歷結(jié)束，arr中存儲的就是單鏈表的最后4個(gè)元素，找到最后一個(gè)元素對應(yīng)的arri，讓k=(i+1)%4，則arrk就是倒數(shù)第4個(gè)元素。static Link GetLast4thOneByArray(Link head) Link curr = head; int i = 0; Link arr = new Link4; while (curr.Next != null) arri = curr.Next; curr = curr.Next; i = (i + 1) % 4; if (arri = null) throw new Exception(Less than 4 elements); return arri;本題目源代碼下載：推而廣之，對倒數(shù)第K個(gè)元素，都能用以上2種算法找出來。3.找出單鏈表的中間元素算法思想：類似于上題，還是使用兩個(gè)指針first和second，只是first每次走一步，second每次走兩步：static Link GetMiddleOne(Link head) Link first = head; Link second = head; while (first != null & first.Next != null) first = first.Next.Next; second = second.Next; return second;但是，這道題目有個(gè)地方需要注意，就是對于鏈表元素個(gè)數(shù)為奇數(shù)，以上算法成立。如果鏈表元素個(gè)數(shù)為偶數(shù)，那么在返回second的同時(shí)，還要返回second.Next也就是下一個(gè)元素，它倆都算是單鏈表的中間元素。下面是加強(qiáng)版的算法，無論奇數(shù)偶數(shù)，一概通殺：static void Main(string args) Link head = GenerateLink(); bool isOdd = true; Link middle = GetMiddleOne(head, ref isOdd); if (isOdd) Console.WriteLine(middle.Data); else Console.WriteLine(middle.Data); Console.WriteLine(middle.Next.Data); Console.Read();static Link GetMiddleOne(Link head, ref bool isOdd) Link first = head; Link second = head; while (first != null & first.Next != null) first = first.Next.Next; second = second.Next; if (first != null) isOdd = false; return second;4.一個(gè)單鏈表，很長，遍歷一遍很慢，我們僅知道一個(gè)指向某節(jié)點(diǎn)的指針curr，而我們又想刪除這個(gè)節(jié)點(diǎn)。這道題目是典型的“貍貓換太子”，如下圖所示：如果不考慮任何特殊情況，代碼就2行：curr.Data = curr.Next.Data;curr.Next = curr.Next.Next;上述代碼由一個(gè)地方需要注意，就是如果要?jiǎng)h除的是最后一個(gè)元素呢？那就只能從頭遍歷一次找到倒數(shù)第二個(gè)節(jié)點(diǎn)了。此外，這道題目的一個(gè)變身就是將一個(gè)環(huán)狀單鏈表拆開（即刪除其中一個(gè)元素），此時(shí)，只要使用上面那兩行代碼就可以了，不需要考慮表尾。相關(guān)問題：只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)q。話說，交換單鏈表任意兩個(gè)節(jié)點(diǎn)，也可以用交換值的方法。但這樣就沒意思了，所以，才會有第7題霸王硬上工的做法。5.兩個(gè)不交叉的有序鏈表的合并有兩個(gè)有序鏈表，各自內(nèi)部是有序的，但是兩個(gè)鏈表之間是無序的。算法思路：當(dāng)然是循環(huán)逐項(xiàng)比較兩個(gè)鏈表了，如果一個(gè)到了頭，就不比較了，直接加上去。注意，對于2個(gè)元素的Data相等（僅僅是Data相等哦，而不是相同的引用），我們可以把它視作前面的Data大于后面的Data，從而節(jié)省了算法邏輯。static Link MergeTwoLink(Link head1, Link head2) Link head = new Link(null, Int16.MinValue); Link pre = head; Link curr = head.Next; Link curr1 = head1; Link curr2 = head2; /compare until one link run to the end while (curr1.Next != null & curr2.Next != null) if (curr1.Next.Data curr2.Next.Data) curr = new Link(null, curr1.Next.Data); curr1 = curr1.Next; else curr = new Link(null, curr2.Next.Data); curr2 = curr2.Next; pre.Next = curr; pre = pre.Next; /if head1 run to the end while (curr1.Next != null) curr = new Link(null, curr1.Next.Data); curr1 = curr1.Next; pre.Next = curr; pre = pre.Next; /if head2 run to the end while (curr2.Next != null) curr = new Link(null, curr2.Next.Data); curr2 = curr2.Next; pre.Next = curr; pre = pre.Next; return head;如果這兩個(gè)有序鏈表交叉組成了Y型呢，比如說：這時(shí)我們需要先找出這個(gè)交叉點(diǎn)（圖中是11），這個(gè)算法參見第9題，我們這里直接使用第10道題目中的方法GetIntersect。然后局部修改上面的算法，只要其中一個(gè)鏈表到達(dá)了交叉點(diǎn)，就直接把另一個(gè)鏈表的剩余元素都加上去。如下所示：static Link MergeTwoLink2(Link head1, Link head2) Link head = new Link(null, Int16.MinValue); Link pre = head; Link curr = head.Next; Link intersect = GetIntersect(head1, head2); Link curr1 = head1; Link curr2 = head2; /compare until one link run to the intersect while (curr1.Next != intersect & curr2.Next != intersect) if (curr1.Next.Data head1 head2 head3 head4 我們的算法思想是： 進(jìn)行兩次遍歷，在外層用curr1遍歷二級單鏈表head，在內(nèi)層用curr2遍歷每個(gè)單鏈表：public static Link GenerateNewLink(CascadeLink head) CascadeLink curr1 = head.NextHead; Link newHead = curr1.Next; Link curr2 = newHead; while (curr1 != null) curr2.Next = curr1.Next.Next; while (curr2.Next != null) curr2 = curr2.Next; curr1 = curr1.NextHead; return newHead;其中，curr2.Next = curr1.Next.Next; 這句話是關(guān)鍵，它負(fù)責(zé)把上一個(gè)單鏈表的表尾和下一個(gè)單鏈表的非空表頭連接起來。7.單鏈表交換任意兩個(gè)元素（不包括表頭）先一次遍歷找到這兩個(gè)元素curr1和curr2，同時(shí)存儲這兩個(gè)元素的前驅(qū)元素pre1和pre2。然后大換血public static Link SwitchPoints(Link head, Link p, Link q) if (p = head | q = head) throw new Exception(No exchange with head); if (p = q) return head; /find p and q in the link Link curr = head; Link curr1 = p; Link curr2 = q; Link pre1 = null; Link pre2 = null; int count = 0;while (curr != null) if (curr.Next = p) pre1 = curr; count+; if (count = 2) break; else if (curr.Next = q) pre2 = curr; count+; if (count = 2) break; curr = curr.Next; curr = curr1.Next; pre1.Next = curr2; curr1.Next = curr2.Next; pre2.Next = curr1; curr2.Next = curr; return head;注意特例，如果相同元素，就沒有必要交換；如果有一個(gè)是表頭，就不交換。8.判斷單鏈表是否有環(huán)？如何找到環(huán)的“起始”點(diǎn)？如何知道環(huán)的長度？算法思想：先分析是否有環(huán)。為此我們建立兩個(gè)指針，從header一起向前跑，一個(gè)步長為1，一個(gè)步長為2，用while（直到步長2的跑到結(jié)尾）檢查兩個(gè)指針是否相等，直到找到為止。static bool JudgeCircleExists(Link head) Link first = head; /1 step each time Link second = head; /2 steps each time while (second.Next != null & second.Next.Next != null) second = second.Next.Next; first = first.Next; if (second = first) return true; return false;那又如何知道環(huán)的長度呢？根據(jù)上面的算法，在返回true的地方，也就是2個(gè)指針相遇處，這個(gè)位置的節(jié)點(diǎn)P肯定位于環(huán)上。我們從這個(gè)節(jié)點(diǎn)開始先前走，轉(zhuǎn)了一圈肯定能回來：static int GetCircleLength(Link point) int length = 1; Link curr = point; while (curr.Next != point) length+; curr = curr.Next; return length;繼續(xù)我們的討論，如何找到環(huán)的“起始”點(diǎn)呢？延續(xù)上面的思路，我們?nèi)匀辉诜祷豻rue的地方P，計(jì)算一下從有環(huán)單鏈表的表頭head到P點(diǎn)的距離static int GetLengthFromHeadToPoint(Link head, Link point) int length = 1; Link curr = head; while (curr != point) length+; curr = curr.Next; return length;如果我們把環(huán)從P點(diǎn)“切開”（當(dāng)然并不是真的切，那就破壞原來的數(shù)據(jù)結(jié)構(gòu)了），那么問題就轉(zhuǎn)化為計(jì)算兩個(gè)相交“單鏈表”的交點(diǎn)（第10題）：一個(gè)單鏈表是從P點(diǎn)出發(fā)，到達(dá)P（一個(gè)回圈），距離M；另一個(gè)單鏈表從有環(huán)單鏈表的表頭head出發(fā)，到達(dá)P，距離N。我們可以參考第10題的GetIntersect方法并稍作修改。private static Link FindIntersect(Link head) Link p = null; /get the point in the circle bool result = JudgeCircleExists(head, ref p); if (!result) return null; Link curr1 = head.Next; Link curr2 = p.Next; /length from head to p int M = 1; while (curr1 != p) M+; curr1 = curr1.Next; /circle length int N = 1; while (curr2 != p) N+; curr2 = curr2.Next; /recover curr1 & curr2 curr1 = head.Next; curr2 = p.Next; /make 2 links have the same distance to the intersect if (M N) for (int i = 0; i M - N; i+) curr1 = curr1.Next; else if (M N) for (int i = 0; i N) for (int i = 0; i M - N; i+) curr1 = curr1.Next; else if (M N) for (int i = 0; i 99NULL + 1NULL = 1000NULL肯定是使用遞歸啦，不然沒辦法解決進(jìn)位+1問題，因?yàn)檫@時(shí)候要讓前面的節(jié)點(diǎn)加1，而我們的單鏈表是永遠(yuǎn)指向前的。此外對于999+1=1000，新得到的值的位數(shù)（4位）比原來的兩個(gè)值（1個(gè)1位，1個(gè)3位）都多，所以我們將表頭的值設(shè)置為0，如果多出一位來，就暫時(shí)存放到表頭。遞歸結(jié)束后，如果表頭為1，就在新的鏈表外再加一個(gè)新的表頭。/head1 length head2, so M Npublic static int Add(Link head1, Link head2, ref Link newHead, int M, int N) / goto the end if (head1 = null) return 0; int temp = 0; int result = 0; newHead = new Link(null, 0); if (M N) result = Add(head1.Next, head2, ref newHead.Next, M - 1, N); temp = head1.Data + result; newHead.Data = temp % 10; return temp = 10 1 : 0; else / M = N result = Add(head1.Next, head2.Next, ref newHead.Next, M - 1, N - 1); temp = head1.Data + head2.Data + +result; newHead.Data = temp % 10; return temp = 10 1 : 0; 這里假設(shè)head1比head2長，而且M、N分別是head1和head2的長度。12.單鏈表排序無外乎是冒泡、選擇、插入等排序方法。關(guān)鍵是交換算法，需要額外考慮。第7題我編寫了一個(gè)交換算法，在本題的排序過程中，我們可以在外層和內(nèi)層循環(huán)里面，捕捉到pre1和pre2，然后進(jìn)行交換，而無需每次交換又要遍歷一次單鏈表。在實(shí)踐中，我發(fā)現(xiàn)冒泡排序和選擇排序都要求內(nèi)層循環(huán)從鏈表的末尾向前走，這明顯是不合時(shí)宜的。所以我最終選擇了插入排序算法，如下所示：先給出基于數(shù)組的算法：代碼static intInsertSort(int arr)for(int i=1; i0)&arrjarrj-1;j-)arrj=arrjarrj-1;arrj-1=arrjarrj-1;arrj=arrjarrj-1;return arr;仿照上面的思想，我們來編寫基于Link的算法：public static Link SortLink(Link head) Link pre1 = head; Link pre2 = head.Next; Link min = null; for (Link curr1 = head.Next; curr1 != null; curr1 = min.Next) if (curr1.Next = null) break; min = curr1; for (Link curr2 = curr1.Next; curr2 != null; curr2 = curr2.Next) /swap curr1 and curr2 if (curr2.Data curr1.Data) min = curr2; curr2 = curr1; curr1 = min; pre1.Next = curr1; curr2.Next = curr1.Next; curr1.Next = pre2; /if exchange element n-1 and n, no need to add reference from pre2 to curr2, because they are the same one if (pre2 != curr2) pre2.Next = curr2; pre2 = curr2; pre1 = min; pre2 = min.Next; return head;值得注意的是，很多人的算法不能交換相鄰兩個(gè)元素，這是因?yàn)閜re2和curr2是相等的，如果此時(shí)還執(zhí)行pre2.Next = curr2; 會造成一個(gè)自己引用自己的環(huán)。交換指針很是麻煩，而且效率也不高，需要經(jīng)常排序的東西最好不要用鏈表來實(shí)現(xiàn)，還是數(shù)組好一些。13.刪除單鏈表中重復(fù)的元素用Hashtable輔助，遍歷一遍單鏈表就能搞定。實(shí)踐中發(fā)現(xiàn)，curr從表頭開始，每次判斷下一個(gè)元素curr.Netx是否重復(fù)，如果重復(fù)直接使用curr.Next = curr.Next.Next; 就可以刪除