【圖解】記一次手撕演算法面試：字節跳動的面試官把我四連擊了
- 2019 年 11 月 30 日
- 筆記
作者：帥地
字節跳動這家公司，應該是所有秋招的公司中，對演算法最重視的一個了，每次面試基本都會讓你手撕演算法，今天這篇文章就記錄下當時被問到的幾個演算法題，並且每個演算法題我都詳細著給出了最優解，下面再現當時的面試場景。看完一定讓你有所收穫
一、小牛試刀：有效括弧
大部分情況下，面試官都會問一個不怎麼難的問題，不過你千萬別太開心，因為這道題往往可以拓展出更多有難度的問題，或者一道題看起來很簡單，但是給出最優解，確實很不容易的。這道題是這樣的
給定一個只包括 '('，')'的字元串，判斷字元串是否有效。註：空字元串屬於有效字元串
示例 1: 輸入: "(())" 輸出: true 實例 2： 輸入: "())(" 輸出: false
第一眼看到這道題，我去，這麼簡單，穩了（因為一面的時候，剛剛被面試官懟過勇者斗惡龍的DP題，在 leetcdoe 屬於 hard 級別）。
其實這道題的 leetcode 第 20 題的簡化版，屬於 easy 級別
於是我也不假思索直接用棧來解決了，相信 99% 都會用棧解決吧？這裡我稍微說以下過程吧，步驟如下：
1、在遍歷字元串的過程中，遇到 "(" 就讓它入棧，遇到 ")" 就判斷下棧裡面有沒有 "(" ，分以下兩種情況：
（1）、如果有，則把處於棧頂的 "(" 彈出，相當於和 ")" 進行匹配，然後繼續往後遍歷字元串
（2）、如果沒有，則匹配失敗。相當於字元串的最前面出現了 ")"，顯然這是不合理的。
2、當字元串遍歷完成，判斷棧是否為空，如果為空則表示字元串有效，否則無效。
為了兼顧小白，我該給你們畫了個圖演示，，，，我太良心了。
在這裡插入圖片描述
程式碼如下所示（Java，不過不是學Java也能看懂）
public static boolean isValid(String s){ if(s == null || s.length() < 1) return true; int n = s.length();// 字元串長度 // 創建一個棧來裝字元 Stack<Character> stack = new Stack<>(); // 遍歷字元串 for(int i = 0; i < n; i++){ // 獲取字元串的第 i 個字元 char c = s.charAt(i); if(c == '('){ stack.push(c); }else{ if(stack.isEmpty()) return false; else stack.pop(); } } // 判斷是否為空 if(stack.isEmpty()) return true; return false; }
二、優化
接著面試官說我這道題的空間複雜度是 O(n)，問我能優化一下嗎？
說實話，如果你做過 leetcode 的第 20 題，可能你的腦子會被定向也不一定，因為那道題用棧來處理就是最優解的了。不過這道題屬於簡化版，其實可以把空間複雜度優化成 O(1)，大家可以想一下哦。
由於我們棧裡面存放的都是**同一種字元 **"(" ，其實我們可以用一個變數來取代棧的，這個變數就記錄 "(" 的個數，遇到 "(" 變數就加 1，遇到 ")" 變數就減 1，棧為空就相當於變數的值為 0。
當時腦子有點不知為啥，就馬上相當這個方法了，於是一分鐘就修改好了程式碼，如下：
public static boolean isValid(String s){ if(s == null || s.length() < 1) return true; int n = s.length();// 字元串長度 // 用來記錄遇到的 "(" 的個數 int sum = 0; // 遍歷字元串 for(int i = 0; i < n; i++){ // 獲取字元串的第 i 個字元 char c = s.charAt(i); if(c == '('){ sum++; }else{ if(sum == 0) return false; else sum--; } } return sum == 0 ? true : false; }
這樣子的話，時間複雜度為 O(n)，空間複雜度為 O(1)。
三、最長有效括弧
接著面試官就繼續就這道題繼續加大難度，問題改為如下
給定一個只包含 '(' 和 ')' 的字元串，找出最長的包含有效括弧的子串的長度。
示例 1: 輸入: "(()" 輸出: 2 解釋: 最長有效括弧子串為 "()" 示例 2: 輸入: ")()())" 輸出: 4 解釋: 最長有效括弧子串為 "()()"
其實這道題就是 leetcode 的原題，第 32 題，難度為 hard。
這道題由於我之前做過，微微一笑，假裝用嚴肅的表情思考一下，然後馬上給出了思路，剛開始我是用暴力法的。
1、暴力法
暴力法其實很簡單，就是最開始把第一個字元當做最長有效括弧的首字元來遍歷字元串，接著把第二個字元當做最長有效括弧的首字元來遍歷字元串，接著把第三個字元……
例如對於 s = "( ) ) ( ( ) )"。
把第一個字元作為首字元，則 max = 2 （遇到第三個字元 ')' 就匹配不了了） 把第二個字元作為首字元，則 max = 0 （一開始就是 ')'，顯然啥也匹配不了） 把第三個字元作為首字元，則 max = 0 把第四個字元作為首字元，則 max = 4 ….. 這種做法的時間複雜度為 O(n^2)，空間複雜度為 O(1)
基本上面那道題一樣，只是做了 n 次遍歷。
接著面試官問，還能優化嗎？
早就知道會問優化的了，我自己之前也做過這道題，於是假裝思考了一下，馬上給出了優化。
2、優化
這道題的優化版本我們仍然是用棧來做，不過入棧的時候，不是讓 "(" 入棧，而是讓 "(" 的下標入棧。步驟如下：
1、先把 -1 放入棧內。（至於為什麼？看到後面你就知道了） 2、、對於遇到的每個 '(' ，我們將它的下標放入棧中。 3、對於遇到的每個 『)』 ，我們彈出棧頂的元素並將當前元素的下標與彈出元素下標作差，得出當前有效括弧字元串的長度。
通過這種方法，我們繼續計算有效子字元串的長度，並最終返回最長有效子字元串的長度。
看不懂？沒事，我弄個例子畫幾個圖，例如 s = "( ) ) ( ( ) )"，並且用變數 max 來保存最長有效字元串的程度，i 表示當前字元串的下標
0、初始化：max = 0; i = 0。-1 放入棧內
1、i = 0，s[i] = '('，下標 i = 0 入棧
2、i = 1，s[i] = ')'，出棧; i – 棧頂元素 = 1 – (-1) = 2，此時 max = 2
3、i = 2，s[i] = ')'，出棧；這個時候要注意：由於 -1 出棧後，棧頂沒有元素了，所以這個時候我們必須把 ')' 的下標入棧，相當於最開始的初始化。
4、i = 3，s[i] = '('，入棧;
5、i = 4，s[i] = '('，入棧;
6、i = 5，s[i] = ')'，出棧；i – 棧頂 = 5 – 3 = 2；此時 max = 2;
7、i = 6，s[i] = ')'，出棧；i – 棧頂 = 6 – 2 = 4；此時 max = 4;
8、遍歷結束，最長有效括弧為 4。
看不大懂？沒事，看下程式碼加深理解勒，程式碼如下：
public int longestValidParentheses(String s) { int max = 0; Stack<Integer> stack = new Stack<>(); stack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { //下標入棧 stack.push(i); } else { // 出棧 stack.pop(); // 看棧頂是否為空，為空的話就不能作差了 if (stack.empty()) { stack.push(i); } else { // i - 棧頂，獲得檔期有效括弧長度 max = Math.max(max, i - stack.peek()); } } } return maxans; }
這種做法的時間複雜度為 O(n)，空間複雜度為 O(n)，能想到用棧來處理，算是很不錯的了。
4、最後一擊
我以為我給出這個解法算是可以的了，面試官應該換一道題的了，然後，面試官又來了一句：還能再優化嗎？。這個時候我陷入了沉思…….
看文章的各位大佬們可以想一想在空間上是否還能優化，因為在時間上是不可能優化的了。
想了一會，居然不可以用棧，優化的方案肯定是類似於上面那道題一樣，用記錄數量的變數來代替棧，然後就被我想出了，具體如下：
實際上，這道題仍然可以像上面那樣，用變數來代替棧來優化，不過這個時候我們需要兩個變數，我們假設變數為 left 和 right。
我們在從從左到右遍歷字元串的過程中，用 left 記錄 '(' 的數量，用 right 記錄 ')' 的數量。並且在遍歷的過程中：
1、如果 left >= right，顯然這個時候 right 個 ')' 都將一定能夠得到匹配。所以當前的有效括弧長度為 2 * right。然後更新 max。
2、如果 left < right，顯然這個時候部分 ')' 一定得不到匹配，此時我們把 left 和 right 都置為 0。
當遍歷完字元串，我們是否就得到最大長度的有效括弧了呢？大家可以想一下
答是不可以的，我們還需要從右到左遍歷計算一下。
為什麼呢？
因為實際上 '(' 和 ')' 其實是等價的，為什麼就不可以倒過來遍歷計算呢？所以，千萬別忽略了哈。
最後的程式碼如下：
public int longestValidParentheses(String s) { int left = 0, right = 0, max = 0; // 從左到右 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, 2 * right); } else if( right > left) { left = right = 0; } } left = right = 0; // 從右到左 for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, 2 * left); } else if (left > right) { left = right = 0; } } return max; }
這種做法的時間複雜度為 O(n)，空間複雜度為 O(1)。
總結
說時候，最後一種方法還是比較難想到了，從這次面試中也可以看出，千萬不要看一道題很簡單，有些題要做出來很簡單，但是，如果要以最優解的方式做出來，難度馬上指數上升。。
如果你後面看不大懂，建議多看幾遍哦，這道題考的頻率還是挺高的，主要是可以做的方法多，每種方法的效率又不一樣，不過我這裡必須給你們的提醒，就是平時在做題的時候，一定要尋找最優解，而不是 ac 了就不管了，應該多看看別人的解法。
——– END ———
