面試必備：高頻演算法題終章「圖文解析 + 範例程式碼」之 矩陣 二進位 + 位運算 + LRU 合集
- 2019 年 10 月 21 日
- 筆記
Attention
秋招接近尾聲，我總結了 牛客、WanAndroid 上，有關筆試面經的帖子中出現的演算法題，結合往年考題寫了這一系列文章，所有文章均與 LeetCode 進行核對、測試。歡迎食用
本文將覆蓋 「二進位」 + 「位運算」 和 Lru 方面的面試演算法題，文中我將給出：
- 面試中的題目
- 解題的思路
- 特定問題的技巧和注意事項
- 考察的知識點及其概念
- 詳細的程式碼和
解析
開始之前，我們先看下會有哪些重點案例：
為了方便大家跟進學習，我在 GitHub 建立了一個倉庫
倉庫地址：超級乾貨！精心歸納影片、歸類、總結，各位路過的老鐵支援一下！給個 Star ！
現在就讓我們開始吧！
矩陣
螺旋矩陣
給定一個包含 m x n 個要素的矩陣，（m 行, n 列），按照螺旋順序，返回該矩陣中的所有要素。
示例 :
輸入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 輸出: [1,2,3,4,8,12,11,10,9,5,6,7]解題思路
我們定義矩陣的第 k 層是到最近邊界距離為 k 的所有頂點。例如，下圖矩陣最外層元素都是第 1 層，次外層元素都是第 2 層，然後是第 3 層的。
[[1, 1, 1, 1, 1, 1, 1], [1, 2, 2, 2, 2, 2, 1], [1, 2, 3, 3, 3, 2, 1], [1, 2, 2, 2, 2, 2, 1], [1, 1, 1, 1, 1, 1, 1]]對於每層，我們從左上方開始以順時針的順序遍歷所有元素，假設當前層左上角坐標是 (text{(r1, c1)})，右下角坐標是 (text{(r2, c2)})。
首先，遍歷上方的所有元素 (r1, c)，按照 c = c1,...,c2 的順序。然後遍歷右側的所有元素 (r, c2)，按照 r = r1+1,...,r2 的順序。如果這一層有四條邊（也就是 r1 < r2 並且 c1 < c2 ），我們以下圖所示的方式遍歷下方的元素和左側的元素。
public List<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> rst = new ArrayList<Integer>(); if(matrix == null || matrix.length == 0) { return rst; } int rows = matrix.length; int cols = matrix[0].length; int count = 0; while(count * 2 < rows && count * 2 < cols){ for (int i = count; i < cols - count; i++) { rst.add(matrix[count][i]); } for (int i = count + 1; i < rows - count; i++) { rst.add(matrix[i][cols - count - 1]); } if (rows - 2 * count == 1 || cols - 2 * count == 1) { // 如果只剩1行或1列 break; } for (int i = cols - count - 2; i >= count; i--) { rst.add(matrix[rows - count - 1][i]); } for (int i = rows - count - 2; i >= count + 1; i--) { rst.add(matrix[i][count]); } count++; } return rst; }判斷數獨是否合法
請判定一個數獨是否有效。該數獨可能只填充了部分數字，其中缺少的數字用 . 表示。
維護一個HashSet用來記同一行、同一列、同一九宮格是否存在相同數字
示例 :
輸入: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 輸出: false 解釋: 除了第一行的第一個數字從 5 改為 8 以外，空格內其他數字均與 示例1 相同。 但由於位於左上角的 3x3 宮內有兩個 8 存在, 因此這個數獨是無效的。說明:
一個有效的數獨（部分已被填充）不一定是可解的。
只需要根據以上規則，驗證已經填入的數字是否有效即可。
給定數獨序列只包含數字 1-9 和字元 '.' 。
給定數獨永遠是 9x9 形式的。`
解題思路
一次迭代
首先，讓我們來討論下面兩個問題：
如何枚舉子數獨？
可以使用 box_index = (row / 3) * 3 + columns / 3，其中 / 是整數除法。
如何確保行 / 列 / 子數獨中沒有重複項？
可以利用 value -> count 哈希映射來跟蹤所有已經遇到的值。
現在，我們完成了這個演算法的所有準備工作：
遍曆數獨。
檢查看到每個單元格值是否已經在當前的行 / 列 / 子數獨中出現過：
如果出現重複，返回 false。
如果沒有，則保留此值以進行進一步跟蹤。
返回 true。
public boolean isValidSudoku(char[][] board) { Set seen = new HashSet(); for (int i=0; i<9; ++i) { for (int j=0; j<9; ++j) { char number = board[i][j]; if (number != '.') if (!seen.add(number + " in row " + i) || !seen.add(number + " in column " + j) || !seen.add(number + " in block " + i / 3 + "-" + j / 3)) return false; } } return true; }旋轉影像
給定一個N×N的二維矩陣表示影像，90度順時針旋轉影像。
示例 :
輸入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]] 輸出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]] 解釋: 首先翻轉每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]； 然後反轉圖片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]說明:
1 <= A.length = A[0].length <= 20 0 <= A[i][j] <= 1解題思路
我們先來看看每個元素在旋轉的過程中是如何移動的：
這提供給我們了一個思路，將給定的矩陣分成四個矩形並且將原問題劃歸為旋轉這些矩形的問題。
現在的解法很直接 — 可以在第一個矩形中移動元素並且在 長度為 4 個元素的臨時列表中移動它們。
public void rotate(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return; } int length = matrix.length; for (int i = 0; i < length / 2; i++) { for (int j = 0; j < (length + 1) / 2; j++){ int tmp = matrix[i][j]; matrix[i][j] = matrix[length - j - 1][i]; matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1]; matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1]; matrix[j][length - i - 1] = tmp; } } }二進位 / 位運算
優點： 特定情況下，計算方便，速度快，被支援面廣 如果用算數方法，速度慢，邏輯複雜 位運算不限於一種語言，它是電腦的基本運算方法知識點預熱
（一）按位與&
兩位全為1，結果才為1
0&0=0；0&1=0；1&0=0；1&1=1
例如：51&5 即 0011 0011 & 0000 0101 =0000 0001 因此51&5=1.
特殊用法
（1）清零。如果想將一個單元清零，即使其全部二進位位為0，只要與一個各位都是零的數值相與，結果為零。
（2）取一個數中指定位。
例如：設 X=10101110，取X的低四位，用X&0000 1111=0000 1110即可得到。
方法：找一個數，對應x要取的位，該數的對應位為1，其餘位為零，此數與x進行「與運算」可以得到x中的指定位。
（二）按位或 |
只要有一個為1，結果就為1。
0|0=0； 0|1=1；1|0=1；1|1=1；
例如：51|5 即0011 0011 | 0000 0101 =0011 0111 因此51|5=55
特殊用法
常用來對一個數據的某些位置1。
方法：找到一個數，對應x要置1的位，該數的對應位為1，其餘位為零。此數與x相或可使x中的某些位置1。
（三）異或 ^
兩個相應位為「異」（值不同），則該位結果為1，否則為0
0^0=0; 0^1=1; 1^0=1; 1^1=0;
例如：51^5 即0011 0011 ^ 0000 0101 =0011 0110 因此51^5=54
特殊用法
（1） 與1相異或，使特定位翻轉
方法：找一個數，對應X要翻轉的位，該數的對應為1，其餘位為零，此數與X對應位異或即可。
例如：X=1010 1110，使X低四位翻轉，用X^0000 1111=1010 0001即可得到。
（2） 與0相異或，保留原值
例如：X^0000 0000 =1010 1110
（3）兩個變數交換值
1.藉助第三個變數來實現
C=A;A=B;B=C;
2.利用加減法實現兩個變數的交換
A=A+B;B=A-B;A=A-B;
3.用位異或運算來實現，也是效率最高的
原理：一個數異或本身等於0 ；異或運算符合交換律
A=A^B;B=A^B;A=A^B
（四）取反與運算~
對一個二進位數按位取反，即將0變為1，1變0
~1=0 ；~0=1（五）左移<<
將一個運算對象的各二進位位全部左移若干位（左邊的二進位位丟棄，右邊補0）
例如： 2<<1 =4 10<<1=100
若左移時捨棄的高位不包含1，則每左移一位，相當於該數乘以2。
例如：
11(1011)<<2= 0010 1100=22 11(00000000 00000000 00000000 1011)整形32bit（六）右移>>
將一個數的各二進位位全部右移若干位，正數左補0，負數左補1，右邊丟棄。若右移時舍高位不是1（即不是負數），操作數每右移一位，相當於該數除以2。
左補0還是補1得看被移數是正還是負。
例如：4>>2=4/2/2=1
-14（即1111 0010）>>2 =1111 1100=-4（七）無符號右移運算>>>
各個位向右移指定的位數，右移後左邊空出的位用零來填充，移除右邊的位被丟棄。
例如：-14>>>2
（即11111111 11111111 11111111 11110010）>>>2
=(00111111 11111111 11111111 11111100)=1073741820
只出現一次的數字
給出 2 * n + 1個數字，除其中一個數字之外其他每個數字均出現兩次，找到這個數字。
異或運算具有很好的性質，相同數字異或運算後為0，並且具有交換律和結合律，故將所有數字異或運算後即可得到只出現一次的數字。
示例 :
輸入: [4,1,2,1,2] 輸出: 4解題思路
如果我們對 0 和二進位位做 XOR 運算，得到的仍然是這個二進位位
(a oplus 0 = a) (a⊕0=a)
如果我們對相同的二進位位做 XOR 運算，返回的結果是 0
(a oplus a = 0) (a⊕a=0)
XOR 滿足交換律和結合律
(a oplus b oplus a = (a oplus a) oplus b = 0 oplus b = ba⊕b⊕a=(a⊕a)⊕b=0⊕b=b)
所以我們只需要將所有的數進行 XOR 操作，得到那個唯一的數字。
public int singleNumber(int[] A) { if(A == null || A.length == 0) { return -1; } int rst = 0; for (int i = 0; i < A.length; i++) { rst ^= A[i]; } return rst; }複雜度分析
時間複雜度： O(n) 。我們只需要將 (text{nums}) 中的元素遍歷一遍，所以時間複雜度就是 (text{nums}) 中的元素個數。
空間複雜度：O(1) 。
格雷編碼
格雷編碼是一個二進位數字系統，在該系統中，兩個連續的數值僅有一個二進位的差異。給定一個非負整數 n ，表示該程式碼中所有二進位的總數，請找出其格雷編碼順序。一個格雷編碼順序必須以 0 開始，並覆蓋所有的 2n 個整數。例子——輸入：2；輸出：[0, 1, 3, 2]；解釋: 0 - 00，1 - 01，3 - 11，2 - 10
解題思路
格雷碼生成公式：G(i) = i ^ (i >> 2)
public ArrayList<Integer> grayCode(int n) { ArrayList<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < (1 << n); i++) { result.add(i ^ (i >> 1)); } return result; }其他
整數反轉
將一個整數中的數字進行顛倒，當顛倒後的整數溢出時，返回 0 (標記為 32 位整數)。
示例 :
輸入: -123 輸出: -321解題思路
利用除 10 取余的方法，將最低位和最高倒序輸出即可
public int reverseInteger(int n) { int reversed_n = 0; while (n != 0) { int temp = reversed_n * 10 + n % 10; n = n / 10; if (temp / 10 != reversed_n) { reversed_n = 0; break; } reversed_n = temp; } return reversed_n; }LRU快取策略
運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 快取機制。它應該支援以下操作： 獲取數據 get 和 寫入數據 put 。
獲取數據 get(key) – 如果密鑰 (key) 存在於快取中，則獲取密鑰的值（總是正數），否則返回 -1。
寫入數據 put(key, value) – 如果密鑰不存在，則寫入其數據值。當快取容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而為新的數據值留出空間。
示例:
LRUCache cache = new LRUCache( 2 /* 快取容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 該操作會使得密鑰 2 作廢 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 該操作會使得密鑰 1 作廢 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4解題思路
解法一：
自定義數據結構：
- 實現一個鏈表用於記錄快取，並處理調用使用頻率
- 定義一個
HashMap用於記錄快取內容
public class LRUCache { private class Node{ Node prev; Node next; int key; int value; public Node(int key, int value) { this.key = key; this.value = value; this.prev = null; this.next = null; } } private int capacity; private HashMap<Integer, Node> hs = new HashMap<Integer, Node>(); private Node head = new Node(-1, -1);// 頭 private Node tail = new Node(-1, -1);// 尾 public LRUCache(int capacity) { this.capacity = capacity; tail.prev = head; head.next = tail; } public int get(int key) { if( !hs.containsKey(key)) { //key找不到 return -1; } // remove current Node current = hs.get(key); current.prev.next = current.next; current.next.prev = current.prev; // move current to tail move_to_tail(current); //每次get，使用次數+1，最近使用，放於尾部 return hs.get(key).value; } public void set(int key, int value) { //數據放入快取 // get 這個方法會把key挪到最末端，因此，不需要再調用 move_to_tail if (get(key) != -1) { hs.get(key).value = value; return; } if (hs.size() == capacity) { //超出快取上限 hs.remove(head.next.key); //刪除頭部數據 head.next = head.next.next; head.next.prev = head; } Node insert = new Node(key, value); //新建節點 hs.put(key, insert); move_to_tail(insert); //放於尾部 } private void move_to_tail(Node current) { //移動數據至尾部 current.prev = tail.prev; tail.prev = current; current.prev.next = current; current.next = tail; } }解法二：
題目要求實現 LRU 快取機制，需要在 O(1)時間內完成如下操作：
- 獲取鍵 / 檢查鍵是否存在
- 設置鍵
- 刪除最先插入的鍵
- 前兩個操作可以用標準的哈希表在
O(1)時間內完成。
有一種叫做有序字典的數據結構，綜合了哈希表和鏈表，在 Java 中為 LinkedHashMap。
下面用這個數據結構來實現。
class LRUCache extends LinkedHashMap<Integer, Integer>{ private int capacity; public LRUCache(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; } }複雜度分析
- 時間複雜度：對於 put 和 get 操作複雜度是 (O(1))，因為有序字典中的所有操作：
get/in/set/move_to_end/popitem（get/containsKey/put/remove）都可以在常數時間內完成。
空間複雜度：(O(capacity))，因為空間只用於有序字典存儲最多 capacity + 1 個元素。
Attention
- 為了提高文章品質，防止冗長乏味
下一部分演算法題
-
本片文章篇幅總結越長。我一直覺得，一片過長的文章，就像一堂超長的 會議/課堂，體驗很不好，所以我打算再開一篇文章
-
在後續文章中，我將繼續針對
鏈表棧隊列堆動態規劃矩陣位運算等近百種，面試高頻演算法題，及其圖文解析 + 教學影片 + 範例程式碼，進行深入剖析有興趣可以繼續關注 _yuanhao 的編程世界 -
不求快，只求優質，每篇文章將以 2 ～ 3 天的周期進行更新，力求保持高品質輸出
# 相關文章
圖文解析 2019 面試演算法題「字元串處理 + 動態規劃 匯總」
「面試原題 + 圖文詳解 + 實例程式碼」二叉搜索樹-雙指針-貪心 面試題匯總
面試高頻演算法題匯總「圖文解析 + 教學影片 + 範例程式碼」之 二分 + 哈希表 + 堆 + 優先隊列 合集
?面試必備：高頻演算法題匯總「圖文解析 + 教學影片 + 範例程式碼」必知必會 排序 + 二叉樹 部分！?
每個人都要學的圖片壓縮終極奧義，有效解決 Android 程式 OOM
Android 讓你的 Room 搭上 RxJava 的順風車 從重複的程式碼中解脫出來
ViewModel 和 ViewModelProvider.Factory：ViewModel 的創建者
單例模式-全局可用的 context 對象，這一篇就夠了
縮放手勢 ScaleGestureDetector 源碼解析，這一篇就夠了
Android 屬性動畫框架 ObjectAnimator、ValueAnimator ，這一篇就夠了
請點贊！因為你的鼓勵是我寫作的最大動力！
為了方便大家跟進學習，我在 GitHub 建立了一個倉庫
倉庫地址：超級乾貨！精心歸納影片、歸類、總結，各位路過的老鐵支援一下！給個 Star ！
