編程面試的10大算法概念匯總

1、編程面試的10大算法概念匯總以卜是在編程而試中排名前10的算法相關(guān)的概念，我會(huì)通過一些簡單的例子來闡述這些概 念。由于完全掌握這些概念需要更多的努力，因此這份列表只是作為一個(gè)介紹。本文將從java的角度看問題，包含下面的這些概念：1. 字符串2. 鏈表3. 樹4. 圖5. 排序6. 遞歸vs.迭代7. 動(dòng)態(tài)規(guī)劃&位操作9. 概率問題10. 排列組合1. 字符串如果ide沒有代碼白動(dòng)補(bǔ)全功能，所以你應(yīng)該記住卜面的這些方法。tochararray()/獲得字符串對(duì)應(yīng)的char數(shù)組arrays.sort() / 數(shù)組排序arrays.tostring(charj a)/ 數(shù)組轉(zhuǎn)成7符串 ch

2、arat(intx)/獲得某個(gè)索引處的字符 length()/字符串長度 length/數(shù)組大小2. 鏈表在java屮,鏈表的實(shí)現(xiàn)非常簡單，每個(gè)節(jié)點(diǎn)node都有一個(gè)值val和指向卜個(gè)節(jié)點(diǎn)的鏈接next。 class node int val;node next;node(int x) val = x;next = null;)鏈農(nóng)兩個(gè)著名的應(yīng)用是棧stack和隊(duì)列queueo 棧:class stacknode top;public node peek() if(top != null) return top;return null;public node pop()if(top = null

3、)return null;elsenode temp = new node(top.val); top = top.next;return temp;public void push(nodc n) if(n != null)n.next = top;top = n;)隊(duì)列:class queue node first, last;public void enqueue(node n) if(first = null)first = n;last = first;elselast.next = n;last = n;)public node dequeue()if(first = null)

4、return null;)elsenode temp = new node(first.val); first = first.next;return temp;)3. 樹這里的樹通常是指二叉樹，每個(gè)節(jié)點(diǎn)都包含一個(gè)左孩了節(jié)點(diǎn)和右孩了節(jié)點(diǎn)，像下面這樣:class treenodejint value;trccnodc left;treenode right;下面是與樹相關(guān)的一些概念:平衡vs.非平衡：平衡二叉樹中，每個(gè)節(jié)點(diǎn)的左右子樹的深度相差至多為1 (1或0)。 滿二叉樹(full binary tree)：除葉子節(jié)點(diǎn)以為的每個(gè)節(jié)點(diǎn)都有兩個(gè)孩子。完美二叉樹(perfect binary tre

5、e)：是具有下列性質(zhì)的滿二叉樹：所有的葉子節(jié)點(diǎn)都有相同 的深度或處在同一層次，且每個(gè)父節(jié)點(diǎn)都必須有兩個(gè)孩了。完全二叉樹(complete binary tree)：二叉樹屮，可能除了最后一個(gè)，每一層都被完全填滿, 且所有節(jié)點(diǎn)都必須盡可能想左靠。譯者注：完美二叉樹也隱約稱為完全二義樹。完美二義樹的一個(gè)例子是一個(gè)人在給定深度的 祖先圖，因?yàn)槊總€(gè)人都一定有兩個(gè)生父母。完全二叉樹町以看成是可以有若干額外向左靠的 葉子節(jié)點(diǎn)的完美二叉樹。疑問：完美二叉樹和滿二叉樹的區(qū)別？(參考： /dads/html7perfectbinarytree.html)4. 圖圖相關(guān)的

6、問題主要集屮在深度優(yōu)先搜索(depth first search)和廣度優(yōu)先搜索(breath first search )o卜市是一個(gè)簡單的圖廣度優(yōu)先搜索的實(shí)現(xiàn)。1) 定義 graphnodeclass graphnode)int val;graphnode next;graphnodej neighbors;boolean visited;graphnodc(int x) val = x;)graphnode(int x, graphnodef n) val = x;neighbors = n;)public string tostring()return "value: h+

7、this.val;2) 定義一個(gè)隊(duì)列queue class queue graphnode first, last;public void cnqucuc(graphnodc n) if(first = null)first = n;last = first;elselast.ncxt = n;last = n;public graphnode dcqucuc()if(first = null)return null;elsegraphnode temp = new graphnode(first.val, first.neighbors); first = first.ncxt;return

8、 temp;3）川隊(duì)列queue實(shí)現(xiàn)廣度優(yōu)先搜索 public class graphtest public static void main(string args) graphnode nl = new graphnode(l);graphnode n2 = new graphnode(2);graphnode n3 = new graphnode(3);graphnode n4 = new graphnode(4);graphnode n5 = new graphnodc(5);n lneighbors = new graphnodelj n2,n3,n5; n2.neighbors =

9、 new graphnode n 1 ,n4;n3.neighbors = new graphnode n 1 ,n4,n5; n4.ncighbors = new graphnodc n2,n3,n5; n5.neighbors = new graphnode n 1 ,n3,n4;brcathfirstscarch(n 1, 5);public static void breathfirstsearch(graphnode root, int x) if(root.val = x)system.out.println(mfind in root11);queue queue = new q

10、ueue();root.visited = true;queue.enqueue(root);whilc(qucuc.first != null)graphnode c = (graphnode) queue.dequeue(); for(graphnode n: c.neighbors)if(!n. visited)system.out.print(n + h");n.visited = true;if(n.val = x)system.out.printlncfind m+n);queue.enqueue(n);輸出:value: 2 value: 3 value: 5 find

11、 value: 5value: 45. 排序卜-面是不同排序算法的時(shí)間復(fù)雜度，你町以去wiki看-卜這些算法的基本思想。algorithmaverage timeworst timespace冒泡排序221選擇排序|221counting sortn+kn+kn+kinsertion sort22quick sortn log(n)merge sortn log(n)n bg(n)depends另外，這里有一些實(shí)現(xiàn)/演示：counting sort、mergesorts quicksortsinsertionsorto/ burt/leaming/c

12、sc51701 /workbook/countingsort.html /quicksort-array-i n-java/ /leetcode-solution-sort-a-linked-list-using-insertion-sort-in -java/ package algorithm.sort; class listnode int val;listnode next;listnode(int x) val = x;next = null;public class sortlinkedlist / merge sortpublic static listnode mergesor

13、tlist(listnode head) if (head = null ii head.next = null)return head;/ count total number of elements int count = 0;listnode p = head;while (p != null) count+;p = p.ncxt;/ break up to two list int middle = count / 2;listnode 1 = head, r = null;listnode p2 = head;int counthalf = 0;while (p2 != null)

14、counthalf+;listnode next = p2.next;訐(counthalf = middle) p2.next = null;r = next;p2 = next;/ now we have two parts 1 andrecursively sort themlistnode hl = mergesortlist(l);listnode h2 = mergesortlist(r);/ merge togetherlistnode merged = merge(h 1, h2);return merged;public static listnode merge(listn

15、ode 1, listnode r) listnode pl = 1;listnode p2 = r;listnode fakchcad = new listnodc(loo);listnode pnew = fakehead;while (pl != null ii p2 != null) if (pl = null) pncw.ncxt = new listnodc(p2.val);p2 = p2.next;pnew = pnew.next; else if (p2 = null) pnew.next = new listnode(pl.val);pl = pl.ncxt;pnew = p

16、new.next; else if (pl.val < p2.val) / if(fakehead)pnew.next = new listnode(pl.val);pl = pl.next;pnew = pnew.next; else if (pl.val = p2.val) pnew.next = new listnode(pl.val); pncw.ncxt.ncxt = new listnodc(pl.val); pnew = pnew.next.next;pl = pl.next;p2 = p2.ncxt; else pnew.next = new listnode(p2.va

17、l); p2 = p2.next;pnew = pnew.next;/ printlist(fakehead.next); return fakehead.next;public static void main(stringlj args) listnode nl = new listnode(2);listnode n2 = new listnode(3);listnode n3 = new listnodc(4);listnode n4 = new listnode(3);listnode n5 = new listnode(4);listnode n6 = new listnode(5

18、);nl.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.ncxt = n6;nl = mergesortlist(n 1); printlist(nl);public static void printlist(listnode x) if(x != null)system.out.print(x.val + m n);while (x.next != null) system.out.print(x.next.val + m h); x = x.next;system.out.printlno;6. 遞歸vs.迭代對(duì)程序員來說，遞歸應(yīng)

19、該是一個(gè)與住俱來的思想(a built-in thought),可以通過一個(gè)簡單的 例子來說明。問題：有n步臺(tái)階，一次只能上1步或2步，共有多少種走法。步驟1：找到走完前n步臺(tái)階和前ml步臺(tái)階z間的關(guān)系。為了走完n步臺(tái)階，只冇兩種方法：從n-1步臺(tái)階爬1步走到或從n-2步臺(tái)階處爬2步走到。 如果f(n)是爬到第n步臺(tái)階的方法數(shù),那么f(n) = f(n-l) + f(n2)。步驟2:確保開始條件是正確的。f(0) = 0;f(l)= 1；public static int f(int n)if(n <= 2) return n;int x = f(n-l) + f(n-2);return

20、 x;遞歸方法的時(shí)間復(fù)雜度是n的指數(shù)級(jí)，因?yàn)橛泻芏嗳哂嗟挠?jì)算，如下:f(5)f(4) + f(3)f(3) + f(2) + f(2) + f(l)f(2) + f(l) + f(2) + f(2) + f(l)直接的想法是將遞歸轉(zhuǎn)換為迭代：public static int f(int n) if (n <= 2)return n;int first = 1, second = 2; int third = 0;for (int i = 3; i <= n; i+) third = first + second;first = second;second = third;retu

21、rn third;對(duì)這個(gè)例子而言,迭代花費(fèi)的時(shí)間更少,你可能也想看看recursion vs iteration o(7. 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃是解決下面這些性質(zhì)類問題的技術(shù)：一個(gè)問題可以通過更小子問題的解決方法來解決（譯者注：即問題的最優(yōu)解包含了其子問題 的最優(yōu)解，也就是最優(yōu)子結(jié)構(gòu)性質(zhì)）。有些子問題的解可能需要計(jì)算多次（譯者注：也就是子問題重疊性質(zhì)）。了問題的解存儲(chǔ)在一張表格里，這樣每個(gè)了問題只用計(jì)算一次。需要額外的空間以節(jié)省時(shí)間。爬臺(tái)階問題完全符合上血的四條性質(zhì)，因此可以用動(dòng)態(tài)規(guī)劃法來解決。public static int a = new int100;public static int f

22、3（int n） if （n <= 2）anj= n;if(an>0)return an;elseanj = f3(n-l ) + f3(n-2);/store results so only calculate once! return anj;8. 位操作位操作符:|0r(|)|and(&)|xor (八)left shift («)right shift (>>)not1|0=11&0=0|10=10010«2=10001100»2=0011卜1=0獲得給定數(shù)字n的第i位：（i從0計(jì)數(shù)并從右邊開始）public sta

23、tic boolean gctbit(int num, int i) int result = num & (l«i);if(result = 0) return false;elsereturn true;例如，獲得數(shù)字10的第2位:i=l, n=101«1= 101010& 10=101() is not 0, so return true;9. 概率問題解決概率相關(guān)的問題通常需要很好的規(guī)劃了解問題(formatting the problem),這里剛好有一 個(gè)這類問題的簡單例了：一個(gè)房間里有50個(gè)人，那么至少有兩個(gè)人生日相同的概率是多少？(忽略閏年的事實(shí)，也 就是一年365天)