Attention
秋招接近尾聲相满，我總結(jié)了 挪阋冢客、WanAndroid 上立美，有關(guān)筆試面經(jīng)的帖子中出現(xiàn)的算法題棕所，結(jié)合往年考題寫了這一系列文章，所有文章均與 LeetCode 進行核對悯辙、測試琳省。歡迎食用
本文將覆蓋 「二進制」 + 「位運算」 和 Lru 方面的面試算法題，文中我將給出：
- 面試中的題目
- 解題的思路
- 特定問題的技巧和注意事項
- 考察的知識點及其概念
- 詳細的代碼和
解析
開始之前躲撰，我們先看下會有哪些重點案例：
為了方便大家跟進學(xué)習(xí)针贬，我在 GitHub 建立了一個倉庫
倉庫地址：超級干貨！精心歸納視頻拢蛋、歸類桦他、總結(jié)，各位路過的老鐵支持一下谆棱！給個 Star 快压！
現(xiàn)在就讓我們開始吧！
矩陣
螺旋矩陣
給定一個包含 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]]
對于每層，我們從左上方開始以順時針的順序遍歷所有元素萎羔，假設(shè)當前層左上角坐標是 液走，右下角坐標是
。
首先贾陷，遍歷上方的所有元素 (r1, c)育灸，按照 c = c1,...,c2 的順序。然后遍歷右側(cè)的所有元素 (r, c2)昵宇，按照 r = r1+1,...,r2 的順序磅崭。如果這一層有四條邊（也就是 r1 < r2 并且 c1 < c2 ），我們以下圖所示的方式遍歷下方的元素和左側(cè)的元素瓦哎。
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;
}
判斷數(shù)獨是否合法
請判定一個數(shù)獨是否有效砸喻。該數(shù)獨可能只填充了部分數(shù)字，其中缺少的數(shù)字用 . 表示蒋譬。
維護一個HashSet用來記同一行割岛、同一列、同一九宮格是否存在相同數(shù)字
示例 :
輸入:
[
["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
解釋: 除了第一行的第一個數(shù)字從 5 改為 8 以外犯助，空格內(nèi)其他數(shù)字均與 示例1 相同癣漆。
但由于位于左上角的 3x3 宮內(nèi)有兩個 8 存在, 因此這個數(shù)獨是無效的。
說明:
一個有效的數(shù)獨（部分已被填充）不一定是可解的剂买。
只需要根據(jù)以上規(guī)則惠爽，驗證已經(jīng)填入的數(shù)字是否有效即可。
給定數(shù)獨序列只包含數(shù)字 1-9 和字符 '.' 瞬哼。
給定數(shù)獨永遠是 9x9 形式的婚肆。`
解題思路
一次迭代
首先，讓我們來討論下面兩個問題：
如何枚舉子數(shù)獨坐慰？
可以使用 box_index = (row / 3) * 3 + columns / 3较性，其中 / 是整數(shù)除法。
如何確保行 / 列 / 子數(shù)獨中沒有重復(fù)項结胀？
可以利用 value -> count 哈希映射來跟蹤所有已經(jīng)遇到的值赞咙。
現(xiàn)在，我們完成了這個算法的所有準備工作：
遍歷數(shù)獨糟港。
檢查看到每個單元格值是否已經(jīng)在當前的行 / 列 / 子數(shù)獨中出現(xiàn)過：
如果出現(xiàn)重復(fù)攀操，返回 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;
}
旋轉(zhuǎn)圖像
給定一個N×N的二維矩陣表示圖像耸别，90度順時針旋轉(zhuǎn)圖像健芭。
示例 :
輸入: [[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]]
解釋: 首先翻轉(zhuǎn)每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
然后反轉(zhuǎn)圖片: [[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
解題思路
我們先來看看每個元素在旋轉(zhuǎn)的過程中是如何移動的：
這提供給我們了一個思路秀姐，將給定的矩陣分成四個矩形并且將原問題劃歸為旋轉(zhuǎn)這些矩形的問題慈迈。
現(xiàn)在的解法很直接 -- 可以在第一個矩形中移動元素并且在 長度為 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;
}
}
}
二進制 / 位運算
優(yōu)點：
特定情況下省有，計算方便痒留，速度快，被支持面廣
如果用算數(shù)方法蠢沿，速度慢伸头，邏輯復(fù)雜
位運算不限于一種語言，它是計算機的基本運算方法
知識點預(yù)熱
（一）按位與&
兩位全為1舷蟀，結(jié)果才為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匈子，只要與一個各位都是零的數(shù)值相與河胎，結(jié)果為零。
（2）取一個數(shù)中指定位虎敦。
例如：設(shè) X=10101110游岳，取X的低四位，用X&0000 1111=0000 1110即可得到其徙。
方法：找一個數(shù)吭历，對應(yīng)x要取的位，該數(shù)的對應(yīng)位為1擂橘，其余位為零晌区，此數(shù)與x進行“與運算”可以得到x中的指定位。
（二）按位或 |
只要有一個為1通贞，結(jié)果就為1朗若。
0|0=0； 0|1=1昌罩；1|0=1哭懈；1|1=1；
例如：51|5 即0011 0011 | 0000 0101 =0011 0111 因此51|5=55
特殊用法
常用來對一個數(shù)據(jù)的某些位置1茎用。
方法：找到一個數(shù)遣总，對應(yīng)x要置1的位睬罗，該數(shù)的對應(yīng)位為1，其余位為零旭斥。此數(shù)與x相或可使x中的某些位置1容达。
（三）異或 ^
兩個相應(yīng)位為“異”（值不同），則該位結(jié)果為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相異或花盐，使特定位翻轉(zhuǎn)
方法：找一個數(shù)，對應(yīng)X要翻轉(zhuǎn)的位菇爪，該數(shù)的對應(yīng)為1算芯，其余位為零，此數(shù)與X對應(yīng)位異或即可凳宙。
例如：X=1010 1110熙揍，使X低四位翻轉(zhuǎn)，用X^0000 1111=1010 0001即可得到氏涩。
（2） 與0相異或诈嘿，保留原值
例如：X^0000 0000 =1010 1110
（3）兩個變量交換值
1.借助第三個變量來實現(xiàn)
C=A;A=B;B=C;
2.利用加減法實現(xiàn)兩個變量的交換
A=A+B;B=A-B;A=A-B;
3.用位異或運算來實現(xiàn)，也是效率最高的
原理：一個數(shù)異或本身等于0 削葱；異或運算符合交換律
A=A^B;B=A^B;A=A^B
（四）取反與運算~
對一個二進制數(shù)按位取反奖亚，即將0變?yōu)?，1變0
~1=0 析砸；~0=1
（五）左移<<
將一個運算對象的各二進制位全部左移若干位（左邊的二進制位丟棄昔字，右邊補0）
例如： 2<<1 =4 10<<1=100
若左移時舍棄的高位不包含1，則每左移一位首繁，相當于該數(shù)乘以2作郭。
例如：
11(1011)<<2= 0010 1100=22
11(00000000 00000000 00000000 1011)整形32bit
（六）右移>>
將一個數(shù)的各二進制位全部右移若干位，正數(shù)左補0弦疮，負數(shù)左補1夹攒，右邊丟棄。若右移時舍高位不是1（即不是負數(shù)）胁塞，操作數(shù)每右移一位咏尝，相當于該數(shù)除以2。
左補0還是補1得看被移數(shù)是正還是負啸罢。
例如：4>>2=4/2/2=1
-14（即1111 0010）>>2 =1111 1100=-4
（七）無符號右移運算>>>
各個位向右移指定的位數(shù)编检，右移后左邊空出的位用零來填充，移除右邊的位被丟棄扰才。
例如：-14>>>2
（即11111111 11111111 11111111 11110010）>>>2
=(00111111 11111111 11111111 11111100)=1073741820
只出現(xiàn)一次的數(shù)字
給出 2 * n + 1個數(shù)字允懂，除其中一個數(shù)字之外其他每個數(shù)字均出現(xiàn)兩次，找到這個數(shù)字衩匣。
異或運算具有很好的性質(zhì)蕾总，相同數(shù)字異或運算后為0粥航，并且具有交換律和結(jié)合律，故將所有數(shù)字異或運算后即可得到只出現(xiàn)一次的數(shù)字生百。
示例 :
輸入: [4,1,2,1,2]
輸出: 4
解題思路
如果我們對 0 和二進制位做 XOR 運算递雀，得到的仍然是這個二進制位
如果我們對相同的二進制位做 XOR 運算，返回的結(jié)果是 0
XOR 滿足交換律和結(jié)合律
所以我們只需要將所有的數(shù)進行 XOR 操作置侍，得到那個唯一的數(shù)字映之。
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;
}
復(fù)雜度分析
時間復(fù)雜度： O(n) 拦焚。我們只需要將 中的元素遍歷一遍蜡坊，所以時間復(fù)雜度就是
中的元素個數(shù)。
空間復(fù)雜度：O(1) 赎败。
格雷編碼
格雷編碼是一個二進制數(shù)字系統(tǒng)秕衙，在該系統(tǒng)中，兩個連續(xù)的數(shù)值僅有一個二進制的差異僵刮。給定一個非負整數(shù) n 据忘，表示該代碼中所有二進制的總數(shù)，請找出其格雷編碼順序搞糕。一個格雷編碼順序必須以 0 開始勇吊，并覆蓋所有的 2n 個整數(shù)。例子——輸入：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;
}
其他
整數(shù)反轉(zhuǎn)
將一個整數(shù)中的數(shù)字進行顛倒，當顛倒后的整數(shù)溢出時碟狞，返回 0 (標記為 32 位整數(shù))啄枕。
示例 :
輸入: -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緩存策略
運用你所掌握的數(shù)據(jù)結(jié)構(gòu)族沃，設(shè)計和實現(xiàn)一個 LRU (最近最少使用) 緩存機制频祝。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。
獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中脆淹，則獲取密鑰的值（總是正數(shù)）智润，否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在未辆，則寫入其數(shù)據(jù)值窟绷。當緩存容量達到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值咐柜，從而為新的數(shù)據(jù)值留出空間兼蜈。
示例:
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
解題思路
解法一：
自定義數(shù)據(jù)結(jié)構(gòu)：
- 實現(xiàn)一個鏈表用于記錄緩存攘残，并處理調(diào)用使用頻率
- 定義一個
HashMap用于記錄緩存內(nèi)容
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，使用次數(shù)+1为狸，最近使用歼郭，放于尾部
return hs.get(key).value;
}
public void set(int key, int value) { //數(shù)據(jù)放入緩存
// get 這個方法會把key挪到最末端，因此辐棒，不需要再調(diào)用 move_to_tail
if (get(key) != -1) {
hs.get(key).value = value;
return;
}
if (hs.size() == capacity) { //超出緩存上限
hs.remove(head.next.key); //刪除頭部數(shù)據(jù)
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value); //新建節(jié)點
hs.put(key, insert);
move_to_tail(insert); //放于尾部
}
private void move_to_tail(Node current) { //移動數(shù)據(jù)至尾部
current.prev = tail.prev;
tail.prev = current;
current.prev.next = current;
current.next = tail;
}
}
解法二：
題目要求實現(xiàn) LRU 緩存機制病曾，需要在 O(1)時間內(nèi)完成如下操作：
- 獲取鍵 / 檢查鍵是否存在
- 設(shè)置鍵
- 刪除最先插入的鍵
- 前兩個操作可以用標準的哈希表在
O(1)時間內(nèi)完成。
有一種叫做有序字典的數(shù)據(jù)結(jié)構(gòu)漾根，綜合了哈希表和鏈表泰涂，在 Java 中為 LinkedHashMap。
下面用這個數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)辐怕。
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;
}
}
復(fù)雜度分析
- 時間復(fù)雜度：對于 put 和 get 操作復(fù)雜度是
逼蒙，因為有序字典中的所有操作：
-
get/in/set/move_to_end/popitem（get/containsKey/put/remove）都可以在常數(shù)時間內(nèi)完成。
空間復(fù)雜度：寄疏，因為空間只用于有序字典存儲最多 capacity + 1 個元素是牢。
Attention
- 為了提高文章質(zhì)量，防止冗長乏味
下一部分算法題
本片文章篇幅總結(jié)越長陕截。我一直覺得驳棱，一片過長的文章，就像一堂超長的 會議/課堂农曲，體驗很不好社搅，所以我打算再開一篇文章
在后續(xù)文章中，我將繼續(xù)針對
鏈表棧隊列堆動態(tài)規(guī)劃矩陣位運算等近百種朋蔫，面試高頻算法題罚渐，及其圖文解析 + 教學(xué)視頻 + 范例代碼，進行深入剖析有興趣可以繼續(xù)關(guān)注 _yuanhao 的編程世界不求快驯妄，只求優(yōu)質(zhì)荷并，每篇文章將以 2 ～ 3 天的周期進行更新，力求保持高質(zhì)量輸出
相關(guān)文章
?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」之 字符串處理+動態(tài)規(guī)劃 合集青扔！
「面試高頻」二叉搜索樹+雙指針+貪心 算法題指北
??面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」之 二分 + 哈希表 + 堆 + 優(yōu)先隊列 合集源织！??
?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」必問之 鏈表 + 棧 + 隊列 部分！??
?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」排序 + 二叉樹 部分微猖！??
歡迎關(guān)注_yuanhao的簡書谈息！
請點贊！因為你的鼓勵是我寫作的最大動力凛剥！
