數據結構和演算法躬行記（2）——棧、隊列、散列表和位運算
- 2020 年 8 月 31 日
- 筆記
- 數據結構和演算法躬行記
一、棧
棧（stack）是一種操作受限的線性表數據結構，基於後進先出（LIFO）策略的集合類型，例如函數中的臨時變數符合後進先出的特性，因此用棧保存最合適。
在入棧和出棧過程中所需的空間複雜度是 O(1)，時間複雜度也是 O(1)。空間複雜度是指運行演算法還需要的額外存儲空間。
注意，記憶體中的堆棧和數據結構中的堆棧不是一個概念，前者是真實存在的物理區，後者是抽象的數據存儲結構。
面試題30 包含min函數的棧。在壓棧時，與之前的最小值比較，每次把兩者較小的那個值存放到輔助棧中。
面試題31 棧的壓入和彈出序列。如果彈出的數字是棧頂，則彈出；如果彈出的數字不在棧頂，則把還沒入棧的數字壓入到輔助棧中，直到棧頂是彈出數字為止。
1）括弧匹配
用正確的類型和順序匹配括弧，例如「(」跟「)」匹配，「[」跟「]」匹配，「{」跟「}」匹配。例題：LeetCode的20. 有效的括弧。
第一種思路是，當遇到匹配的最小括弧對時，將它們從棧中刪除（即出棧），如果最後棧為空，那麼它是有效的括弧，反之不是，程式碼如下所示。
function isValidParentheses(s) { const length = s.length; let i = 0; const stack = []; while (i < length) { let stackLen = stack.length > 0 ? stack.length - 1 : stack.length; if ( (stack[stackLen] == "(" && s[i] == ")") || (stack[stackLen] == "{" && s[i] == "}") || (stack[stackLen] == "[" && s[i] == "]") ) { stack.pop(); i++; continue; } stack.push(s[i]); i++; } return stack.length === 0; }
第二種思路是巧妙的利用一張映射表，以右括弧為鍵，左括弧為值。先判斷當前字元是否是左括弧，若是，就入棧，否則匹配當前棧頂元素是否與當前字元匹配。
function isValidParentheses(s) { const stack = [], map = { "}": "{", "]": "[", ")": "(" }; for (let i = 0, len = s.length; i < len; i++) { let c = s[i]; if (!map[c]) { stack.push(c); continue; } if (stack.length > 0 && map[c] != stack.pop()) return false; } return stack.length == 0; }
2）算術表達式求值
( 1 + ( 2 + 3 ) * ( 4 * 5 ) ) 是一個算術表達式，如果將4乘以5，把3加上2，取它們的積然後加1，就得到了101。
表達式由括弧、運算符和操作數（數字）組成，可以用兩個棧分別保存運算符和操作數來完成算術求值，處理過程如下所列。
（1）將操作數壓入操作數棧；
（2）將運算符壓入運算符棧；
（3）忽略左括弧；
（4）在遇到右括弧時，彈出一個運算符，彈出所需數量的操作數，並將運算符和操作數的運算結果壓入操作數棧。
源碼如下所示。例題：LeetCode的150. 逆波蘭表達式求值。
function evalExpress(s) { const length = s.length; let i = 0; const ops = [], vals = []; while (i < length) { let word = s[i]; if (word == "(") { } else if (word == "+" || word == "-" || word == "*" || word == "/") ops.push(word); else if (word == ")") { let op = ops.pop(), val = vals.pop(); if (op == "+") val = vals.pop() + val; else if (op == "-") val = vals.pop() - val; else if (op == "*") val = vals.pop() * val; else if (op == "/") val = vals.pop() / val; vals.push(val); } else vals.push(parseInt(word)); i++; } return vals.pop(); }
二、隊列
隊列（queue）也是一種操作受限的線性表數據結構，基於先進先出（FIFO）策略的集合類型，隊列的應用非常廣泛，例如循環隊列、阻塞隊列、並發隊列等。
棧只需一個棧頂指針，而隊列需要兩個：隊首指針和隊尾指針。
面試題9 用兩個棧實現隊列。先進後出的棧實現先進先出的隊列，一系列棧的壓入和彈出模擬隊列。
面試題59 窗口滑動的最大值。只把可能成為滑動窗口最大值的數存入一個兩端開口的隊列（deque）。延伸題：隊列的最大值。
1）循環隊列
循環隊列是首尾相連的隊列，這樣可避免在出隊時進行數據搬移的操作，但需要準確的判斷出隊空和隊滿，如下所示。例題：LeetCode的641. 設計循環雙端隊列。
class CircularQueue { constructor(capacity) { this.items = []; this.n = capacity; //隊列大小 this.head = 0; //隊首指針 this.tail = 0; //隊尾指針 } enqueue(item) { const { head, tail, n } = this; //隊滿 if ((tail + 1) % n == head) return false; this.items[tail] = item; //隊尾沒有存儲數據，會浪費一個數組的存儲空間 this.tail = (tail + 1) % n; return true; } dequeue() { const { head, tail, n, items } = this; //隊空 if (head == tail) return null; const result = items[head]; this.head = (head + 1) % n; return result; } }
三、散列表
散列表（Hash Table）也叫哈希表，一種以空間換時間的方式，是數組的擴展，可根據鍵（Key）而直接訪問記憶體儲存位置的數據結構。
它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，提升查找速度。
這個映射函數稱做散列函數，存放記錄的數組稱做散列表。
散列函數的特點如下：
（1）計算得到的結果是一個非負整數。
（2）如果 key1 = key2，那 hash(key1) == hash(key2)。
（3）如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
但即使是著名的MD5、SHA等散列演算法，也不能避免散列衝突。當出現衝突時，可採用拉鏈法（Chaining）和線性探測法（Linear Probing）。
所以在散列表中查找數據，最好情況是 O(1)，最壞情況是 O(n)。
LeetCode的242. 有效的字母異位詞，除了排序字元之外，還可用散列表記錄字元出現的次數。
LeetCode的1. 兩數之和，將數組放入一個散列表中，用總數減去遍歷的值，判斷差是否可在散列表中查到。複雜度升級後的例題：15. 三數之和、18. 四數之和。
四、位運算
位運算就是直接對整數在記憶體中的二進位進行操作。由於位運算不需要轉成十進位，因此處理速度非常快。位運算的總結摘錄於《演算法面試通關40講》。
XOR（異或）的特點如下：
x^0 = x x^1s = ~x; //1s是一種全為1的數，即1s = ~0 x^(~x) = 1s; x^x = 0; a^b=c => a^c=b, b^c=a //swap a^b^c = a^(b^c) = (a^b)^c
常用的位運算包括：
x&1 == 1 OR == 0 //判斷奇偶（x%2==1）。 x = x&(x-1) //將最低位的 1 清零。 x & -x //得到最低位的 1。
更複雜的位運算包括：
x & (~0 << n) //將x最右邊的n位清零 (x >> n) & 1 //獲取x的第n位值（0或1） x & (1 << (n-1)) //獲取x的第n位的冪值 x | (1 << n) //僅將第n位置為1 x & (~(1 << n)) //僅將第n位置為0 x & ((1 << n) - 1) //將x最高位至第n位（含）清零 x & (~((1 << (n+1)) - 1)) //將第n位至第0位（含）清零
LeetCoded的191. 位1的個數，循環執行 x&(x-1)，並且記錄循環次數，判斷條件是x和0是否相同。
LeetCoded的231. 2的冪，仍然使用 x&(x-1)，然後判斷x是否等於0。
LeetCoded的338. 比特位計數，使用遞推公式 count[i] = count[i&(i-1)] + 1，只需一遍循環就能得出1的數量。
