🔥 面試必備：高頻演算法題匯總「圖文解析 + 教學影片 + 範例程式碼」必問之 鏈表 + 棧 + 隊列 部分！🔥
- 2019 年 10 月 13 日
- 筆記
鏈表
鏈表是最基本的數據結構，面試官也常常用鏈表來考察面試者的基本能力，而且鏈表相關的操作相對而言比較簡單，也適合考察寫程式碼的能力。鏈表的操作也離不開指針，指針又很容易導致出錯。
綜合多方面的原因，鏈表題目在面試中佔據著很
重要的地位。
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }刪除節點
思路：
- 將
下一個節點複製到當前
public void deleteNode(ListNode node) { if (node.next == null){ node = null; return; } // 取締下一節點 node.val = node.next.val node.next = node.next.next }翻轉鏈表
思路
思路：每次都將原第一個結點之後的那個結點放在新的表頭後面。
比如1,2,3,4,5
- 第一次：把第一個
結點1後邊的結點2放到新表頭後面，變成2,1,3,4,5 - 第二次：把第一個
結點1後邊的結點3放到新表頭後面，變成3,2,1,4,5 - ……
- 直到： 第一個
結點1，後邊沒有結點為止。
影片
大聖演算法 翻轉鏈表(Reverse Linked List ) — LeetCode 206
public ListNode reverse(ListNode head) { //prev表示前繼節點 ListNode prev = null; while (head != null) { //temp記錄下一個節點，head是當前節點 ListNode temp = head.next; head.next = prev; prev = head; head = temp; } return prev; }中間元素
思路
我總結了一下，可以稱為 田忌賽馬』法
public ListNode findMiddle(ListNode head){ if(head == null){ return null; } ListNode slow = head; ListNode fast = head; // fast.next = null 表示 fast 是鏈表的尾節點 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }合併兩個已排序鏈表
思路
- 遞歸方法：首先比較給新鏈表
接上一個結點，然後這個結點的next就是剩下的兩條鏈表合併的結果。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode lastNode = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { lastNode.next = l1; l1 = l1.next; } else { lastNode.next = l2; l2 = l2.next; } lastNode = lastNode.next; } if (l1 != null) { lastNode.next = l1; } else { lastNode.next = l2; } return dummy.next; }鏈表排序
歸併排序
-
歸併排序的也是基於分治的思想，但是與快排不同的是歸併是先劃分，然後從底層開始向上合併。 -
歸併排序的主要思想是將兩個
已經排好序的分段合併成一個有序的分段。除了找到中間節點的操作必須遍歷鏈表外，其它操作與數組的歸併排序基本相同。
影片
public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } // 取得中間節點，將鏈表一分為二 ListNode mid = findMiddle(head); ListNode right = sortList(mid.next); mid.next = null; ListNode left = sortList(head); return mergeTwoLists(left, right); } // 查找中間元素演算法 public ListNode findMiddle(ListNode head){ if(head == null){ return null; } ListNode slow = head; ListNode fast = head; // fast.next = null 表示 fast 是鏈表的尾節點 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } // 合併兩個有序鏈表 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode lastNode = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { lastNode.next = l1; l1 = l1.next; } else { lastNode.next = l2; l2 = l2.next; } lastNode = lastNode.next; } if (l1 != null) { lastNode.next = l1; } else { lastNode.next = l2; } return dummy.next; }快速排序
快速排序的主要思想是：
-
選定一個
基準元素 -
經過一趟排序，將所有元素分成
兩部分 -
分別對兩部分重複上述操作，直到所有元素都已排序成功
因為單鏈表只能從鏈表頭節點向後遍歷，沒有prev指針，因此必須選擇頭節點作為基準元素。這樣第二步操作的時間複雜度就為O(n)。由於之後都是分別對兩部分完成上述操作，因此會將鏈表劃分為lgn個段，因此時間複雜度為O(nlgn）
public ListNode sortList(ListNode head) { quickSort(head, null); return head; } private void quickSort(ListNode start, ListNode end) { if (start == end) { return; } ListNode pt = partition(start, end); quickSort(start, pt); quickSort(pt.next, end); } // 快排 輪狀法 private ListNode partition(ListNode start, ListNode end) { int pivotKey = start.val; ListNode p1 = start, p2 = start.next; while (p2 != end) { if (p2.val < pivotKey) { p1 = p1.next; swapValue(p1, p2); } p2 = p2.next; } swapValue(start, p1); return p1; } private void swapValue(ListNode node1, ListNode node2) { int tmp = node1.val; node1.val = node2.val; node2.val = tmp; }兩個鏈表是否相交
思路
-
如果兩個單鏈表有
共同的節點 -
那麼從第一個節點開始，後面的節點都會
重疊，直至鏈表結束 -
因為兩個鏈表中有一個
共同節點 -
則從這個節點裡的
指針域指向下一個節點的地址就相同 -
所以
相交以後的節點就會相同，直至鏈表結束，總的模型就像一個「Y」
影片
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode currA = headA; ListNode currB = headB; int lengthA = 0; int lengthB = 0; // 讓長的先走到剩餘長度和短的一樣 while (currA != null) { currA = currA.next; lengthA++; } while (currB != null) { currB = currB.next; lengthB++; } currA = headA; currB = headB; while (lengthA > lengthB) { currA = currA.next; lengthA--; } while (lengthB > lengthA) { currB = currB.next; lengthB--; } // 然後同時走到第一個相同的地方 while (currA != currB) { currA = currA.next; currB = currB.next; } // 返回交叉開始的節點 return currA; }棧 / 隊列
- 棧（stack）又名堆棧：
它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
- 隊列是一種特殊的線性表
特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
帶最小值操作的棧
這道面試題主要考察我們對於輔助棧的使用。
常見的輔助棧包括兩種：
-
輔助棧和數據棧同步
-
輔助棧和數據棧不同步
我們這裡採用輔助棧和數據棧同步的方式：
特點：編碼簡單，不用考慮一些邊界情況，就有一點不好：輔助棧可能會存一些「不必要」的元素。
-
輔助棧為空的時候，必須放入新進來的數；
-
新來的數小於或者等於輔助棧棧頂元素的時候，才放入，特別注意這裡「等於」要考慮進去，因為出棧的時候，連續的、相等的並且是最小值的元素要同步出棧；
-
出棧的時候，輔助棧的棧頂元素等於數據棧的棧頂元素，才出棧。
總結一下：出棧時，最小值出棧才同步；入棧時，最小值入棧才同步。
public class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; // 維護一個輔助棧，傳入當前棧的最小值 public MinStack() { stack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int number) { stack.push(number); if (minStack.isEmpty()) { minStack.push(number); } else { minStack.push(Math.min(number, minStack.peek())); } } public int pop() { minStack.pop(); return stack.pop(); } public int min() { return minStack.peek(); } }有效括弧
思路：
-
初始化棧 S。
-
一次處理表達式的每個括弧。
-
如果遇到開括弧，我們只需將其推到棧上即可。這意味著我們將稍後處4理它，讓我們簡單地轉到前面的 子表達式。
-
如果我們遇到一個閉括弧，那麼我們檢查棧頂的元素。如果棧頂的元素是一個 相同類型的 左括弧，那麼我們將它從棧中彈出並繼續處理。否則，這意味著表達式無效。
-
如果到最後我們剩下的棧中仍然有元素，那麼這意味著表達式無效。
影片
public boolean isValidParentheses(String s) { Stack<Character> stack = new Stack<Character>(); for (Character c : s.toCharArray()) { if ("({[".contains(String.valueOf(c))) { stack.push(c); } else { if (!stack.isEmpty() && isValid(stack.peek(), c)) { stack.pop(); } else { return false; } } } return stack.isEmpty(); } private boolean isValid(char c1, char c2) { return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') || (c1 == '[' && c2 == ']'); }用棧實現隊列
思路：
-
思路是有兩個棧，一個用來放數據（數據棧），一個用來輔助（輔助棧）。
-
數據添加時，會依次壓人棧，取數據時肯定會取棧頂元素，但我們想模擬隊列的先進先出，所以就得取棧底元素，那麼輔助棧就派上用場了
-
把數據棧的元素依次彈出到輔助棧，但保留最後一個元素，最後數據棧就剩下了最後一個元素，直接把元素返回，這時數據棧已經沒有了數據。
-
最後呢，把輔助棧的元素依次壓人數據棧，這樣，我們成功取到了棧底元素。
影片
public class MyQueue { private Stack<Integer> outStack; private Stack<Integer> inStack; public MyQueue() { outStack = new Stack<Integer>(); inStack = new Stack<Integer>(); } private void in2OutStack(){ while(!inStack.isEmpty()){ outStack.push(inStack.pop()); } } public void push(int element) { inStack.push(element); } public int pop() { if(outStack.isEmpty()){ this.in2OutStack(); } return outStack.pop(); } public int top() { if(outStack.isEmpty()){ this.in2OutStack(); } return outStack.peek(); } }逆波蘭表達式求值 (後綴)
思路：
-
逆波蘭表達式求解,定義一個棧輔助計算
-
當遇到運算符"+"、"-"、"*"、"/"時,從棧中pop出兩個數字計算,否則將數字入棧;
public int evalRPN(String[] tokens) { Stack<Integer> s = new Stack<Integer>(); String operators = "+-*/"; for (String token : tokens) { if (!operators.contains(token)) { s.push(Integer.valueOf(token)); continue; } // 這裡有個坑 int a = s.pop(); int b = s.pop(); // 先出的在運算符後 // 後出的在運算符前 if (token.equals("+")) { s.push(b + a); } else if(token.equals("-")) { s.push(b - a); } else if(token.equals("*")) { s.push(b * a); } else { s.push(b / a); } } return s.pop(); }Attention
為了提高文章品質，防止冗長乏味
下一部分演算法題
-
本片文章篇幅總結越長。我一直覺得，一片過長的文章，就像一場超長的 會議/課堂，體驗很不好，所以打算再開一篇文章來總結其餘的考點
-
在後續文章中，我將繼續針對
鏈表棧隊列堆動態規劃矩陣位運算等近百種，面試高頻演算法題，及其圖文解析 + 教學影片 + 範例程式碼，進行深入剖析有興趣可以繼續關注 _yuanhao 的編程世界
相關文章
?面試必備：高頻演算法題匯總「圖文解析 + 教學影片 + 範例程式碼」必知必會 排序 + 二叉樹 部分！?
每個人都要學的圖片壓縮終極奧義，有效解決 Android 程式 OOM
Android 讓你的 Room 搭上 RxJava 的順風車 從重複的程式碼中解脫出來
ViewModel 和 ViewModelProvider.Factory：ViewModel 的創建者
單例模式-全局可用的 context 對象，這一篇就夠了
縮放手勢 ScaleGestureDetector 源碼解析，這一篇就夠了
Android 屬性動畫框架 ObjectAnimator、ValueAnimator ，這一篇就夠了
看完這篇再不會 View 的動畫框架，我跪搓衣板
看完這篇還不會 GestureDetector 手勢檢測，我跪搓衣板！
android 自定義控制項之-繪製鐘錶盤
歡迎關注_yuanhao的部落格園！
為了方便大家跟進學習，我在 GitHub 建立了一個倉庫
倉庫地址：超級乾貨！精心歸納影片、歸類、總結，各位路過的老鐵支援一下！給個 Star ！
