摘要:滿二叉樹除葉子節點以為的每個節點都有兩個孩子。完全二叉樹可以看成是可以有若干額外向左靠的葉子節點的完美二叉樹。
以下是在編程面試中排名前10的算法相關的概念,我會通過一些簡單的例子來闡述這些概念。由于完全掌握這些概念需要更多的努力,因此這份列表只是作為一個介紹。本文將從Java的角度看問題,包含下面的這些概念:
字符串
鏈表
樹
圖
排序
遞歸 vs. 迭代
動態規劃
位操作
概率問題
排列組合
1. 字符串toCharArray() // 獲得字符串對應的char數組 Arrays.sort() // 數組排序 Arrays.toString(char[] a) // 數組轉成字符串 charAt(int x) // 獲得某個索引處的字符 length() // 字符串長度 length // 數組大小2. 鏈表
在Java中,鏈表的實現非常簡單,每個節點Node都有一個值val和指向下個節點的鏈接next。
class Node { int val; Node next; Node(int x) { val = x; next = null; } }
鏈表兩個著名的應用是棧Stack和隊列Queue。
棧:
class Stack{ Node top; public Node peek(){ if(top != null){ return top; } return null; } public Node pop(){ if(top == null){ return null; }else{ Node temp = new Node(top.val); top = top.next; return temp; } } public void push(Node n){ if(n != null){ n.next = top; top = n; } } }
隊列:
class Queue{ Node first, last; public void enqueue(Node n){ if(first == null){ first = n; last = first; }else{ last.next = n; last = n; } } public Node dequeue(){ if(first == null){ return null; }else{ Node temp = new Node(first.val); first = first.next; return temp; } } }3. 樹
這里的樹通常是指二叉樹,每個節點都包含一個左孩子節點和右孩子節點,像下面這樣:
class TreeNode{ int value; TreeNode left; TreeNode right; }
下面是與樹相關的一些概念:
平衡 vs. 非平衡:平衡二叉樹中,每個節點的左右子樹的深度相差至多為1(1或0)。
滿二叉樹(Full Binary Tree):除葉子節點以為的每個節點都有兩個孩子。
完美二叉樹(Perfect Binary Tree):是具有下列性質的滿二叉樹:所有的葉子節點都有相同的深度或處在同一層次,且每個父節點都必須有兩個孩子。
完全二叉樹(Complete Binary Tree):二叉樹中,可能除了最后一個,每一層都被完全填滿,且所有節點都必須盡可能想左靠。
譯者注:完美二叉樹也隱約稱為完全二叉樹。完美二叉樹的一個例子是一個人在給定深度的祖先圖,因為每個人都一定有兩個生父母。完全二叉樹可以看成是可以有若干額外向左靠的葉子節點的完美二叉樹。疑問:完美二叉樹和滿二叉樹的區別?(參考:http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html)
4. 圖圖相關的問題主要集中在深度優先搜索(depth first search)和廣度優先搜索(breath first search)。
下面是一個簡單的圖廣度優先搜索的實現。
1) 定義GraphNode
class GraphNode{ int val; GraphNode next; GraphNode[] neighbors; boolean visited; GraphNode(int x) { val = x; } GraphNode(int x, GraphNode[] n){ val = x; neighbors = n; } public String toString(){ return "value: "+ this.val; } }
2) 定義一個隊列Queue
class Queue{ GraphNode first, last; public void enqueue(GraphNode n){ if(first == null){ first = n; last = first; }else{ last.next = n; last = n; } } public GraphNode dequeue(){ if(first == null){ return null; }else{ GraphNode temp = new GraphNode(first.val, first.neighbors); first = first.next; return temp; } } }
3) 用隊列Queue實現廣度優先搜索
public class GraphTest { public static void main(String[] args) { GraphNode n1 = new GraphNode(1); GraphNode n2 = new GraphNode(2); GraphNode n3 = new GraphNode(3); GraphNode n4 = new GraphNode(4); GraphNode n5 = new GraphNode(5); n1.neighbors = new GraphNode[]{n2,n3,n5}; n2.neighbors = new GraphNode[]{n1,n4}; n3.neighbors = new GraphNode[]{n1,n4,n5}; n4.neighbors = new GraphNode[]{n2,n3,n5}; n5.neighbors = new GraphNode[]{n1,n3,n4}; breathFirstSearch(n1, 5); } public static void breathFirstSearch(GraphNode root, int x){ if(root.val == x) System.out.println("find in root"); Queue queue = new Queue(); root.visited = true; queue.enqueue(root); while(queue.first != null){ GraphNode c = (GraphNode) queue.dequeue(); for(GraphNode n: c.neighbors){ if(!n.visited){ System.out.print(n + " "); n.visited = true; if(n.val == x) System.out.println("Find "+n); queue.enqueue(n); } } } } }
Output:
value: 2 value: 3 value: 5 Find value: 5 value: 45. 排序
下面是不同排序算法的時間復雜度,你可以去wiki看一下這些算法的基本思想。
Algorithm | Average Time | Worst Time | Space |
---|---|---|---|
冒泡排序 | n^2 | n^2 | 1 |
選擇排序 | n^2 | n^2 | 1 |
Counting Sort | n+k | n+k | n+k |
Insertion sort | n^2 | n^2 | |
Quick sort | n log(n) | n^2 | |
Merge sort | n log(n) | n log(n) | depends |
另外,這里有一些實現/演示:: Counting sort、Mergesort、 Quicksort、 InsertionSort。
《視覺直觀感受 7 種常用的排序算法》
《視頻: 6分鐘演示15種排序算法》
6. 遞歸 vs. 迭代對程序員來說,遞歸應該是一個與生俱來的思想(a built-in thought),可以通過一個簡單的例子來說明。
問題: 有n步臺階,一次只能上1步或2步,共有多少種走法。
步驟1:找到走完前n步臺階和前n-1步臺階之間的關系。
為了走完n步臺階,只有兩種方法:從n-1步臺階爬1步走到或從n-2步臺階處爬2步走到。如果f(n)是爬到第n步臺階的方法數,那么f(n) = f(n-1) + f(n-2)。
步驟2: 確保開始條件是正確的。
f(0) = 0;
f(1) = 1;
public static int f(int n){ if(n <= 2) return n; int x = f(n-1) + f(n-2); return x; }
遞歸方法的時間復雜度是n的指數級,因為有很多冗余的計算,如下:
f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
直接的想法是將遞歸轉換為迭代:
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; } return third; }
對這個例子而言,迭代花費的時間更少,你可能也想看看Recursion vs Iteration。
7. 動態規劃動態規劃是解決下面這些性質類問題的技術:
一個問題可以通過更小子問題的解決方法來解決(譯者注:即問題的最優解包含了其子問題的最優解,也就是最優子結構性質)。
有些子問題的解可能需要計算多次(譯者注:也就是子問題重疊性質)。
子問題的解存儲在一張表格里,這樣每個子問題只用計算一次。
需要額外的空間以節省時間。
爬臺階問題完全符合上面的四條性質,因此可以用動態規劃法來解決。
public static int[] A = new int[100]; public static int f3(int n) { if (n <= 2) A[n]= n; if(A[n] > 0) return A[n]; else A[n] = f3(n-1) + f3(n-2);//store results so only calculate once! return A[n]; }8. 位操作
OR (I) | AND (&) | XOR (^) | Left Shift (<<) | Right Shift (>>) | Not (~) |
---|---|---|---|---|---|
1 | 0=1 | 1&0=0 | 1^0=1 | 0010<<2=1000 | 1100>>2=0011 | ~1=0 |
獲得給定數字n的第i位:(i從0計數并從右邊開始)
public static boolean getBit(int num, int i){ int result = num & (1<例如,獲得數字10的第2位:
9. 概率問題
i=1, n=10
1<<1= 10
1010&10=10
10 is not 0, so return true;解決概率相關的問題通常需要很好的規劃了解問題(formatting the problem),這里剛好有一個這類問題的簡單例子:
一個房間里有50個人,那么至少有兩個人生日相同的概率是多少?(忽略閏年的事實,也就是一年365天)
計算某些事情的概率很多時候都可以轉換成先計算其相對面。在這個例子里,我們可以計算所有人生日都互不相同的概率,也就是:365/365 + 364/365 + 363/365 + 365-n/365 + 365-49/365,這樣至少兩個人生日相同的概率就是1 – 這個值。
public static double caculateProbability(int n){ double x = 1; for(int i=0; icalculateProbability(50) = 0.97
10. 排列組合組合和排列的區別在于次序是否關鍵。
如果你有任何問題請在下面評論。
參考/推薦資料:
1. Binary tree
2. Introduction to Dynamic Programming
3. UTSA Dynamic Programming slides
4. Birthday paradox
5. Cracking the Coding Interview: 150 Programming Interview Questions and Solutions, Gayle Laakmann McDowell
原文 Top 10 Algorithms for Coding Interview
轉自 伯樂在線 - 敏敏
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64001.html
摘要:如問到是否使用某框架,實際是是問該框架的使用場景,有什么特點,和同類可框架對比一系列的問題。這兩個方向的區分點在于工作方向的側重點不同。 [TOC] 這是一份來自嗶哩嗶哩的Java面試Java面試 32個核心必考點完全解析(完) 課程預習 1.1 課程內容分為三個模塊 基礎模塊: 技術崗位與面試 計算機基礎 JVM原理 多線程 設計模式 數據結構與算法 應用模塊: 常用工具集 ...
摘要:下面是一些常見的理解性問題,每一個問題盡量用圖或代碼去描述。內容全部來自,包括基本語法數組集合類泛型面向對象垃圾回收異常控制輸入輸出和內存。不斷更新,歡迎大家提出有趣味的問題和意見。 程序員經常可以通過搜索或者記憶來完成代碼,但是許多時候并不真正理解為什么那樣寫。也就是說,有一定經驗的程序員不會犯一些低級的語法錯誤,但是因為不深入理解有可能造成一些高級錯誤,比如說運行無效率,代碼難De...
摘要:特意對前端學習資源做一個匯總,方便自己學習查閱參考,和好友們共同進步。 特意對前端學習資源做一個匯總,方便自己學習查閱參考,和好友們共同進步。 本以為自己收藏的站點多,可以很快搞定,沒想到一入匯總深似海。還有很多不足&遺漏的地方,歡迎補充。有錯誤的地方,還請斧正... 托管: welcome to git,歡迎交流,感謝star 有好友反應和斧正,會及時更新,平時業務工作時也會不定期更...
摘要:十年鏟碼,八大體系超千篇數百萬字技術筆記系列匯總悅享版十年鏟碼兩茫茫,縱思量,卻易忘不覺筆者步入程序員已有十年。十年之期,正巧筆者從阿里離開,重回打印制造業的懷抱,希望能依托于設備優勢逐步真正構建分布式制造網絡。 showImg(https://segmentfault.com/img/remote/1460000020151971); 十年鏟碼,八大體系超千篇數百萬字技術筆記系列匯總...
閱讀 2581·2021-11-22 12:01
閱讀 1105·2021-11-15 11:37
閱讀 3685·2021-09-22 14:59
閱讀 1746·2021-09-04 16:45
閱讀 1382·2021-09-03 10:30
閱讀 1013·2021-08-11 11:18
閱讀 2459·2019-08-30 10:53
閱讀 2013·2019-08-29 15:13