記一次手撕算法面試：字節(jié)跳動的面試官把我四連擊了

taotao_2016 2020-02-07

展開全文

來自公眾號：帥地玩編程
作者：帥地
個人簡介：一個熱愛編程的在校生，我的世界不只有coding，還有writing。目前維護訂閱號「苦逼的碼農(nóng)」，專注于寫「算法與數(shù)據(jù)結(jié)構(gòu)」，「Java」,「計算機網(wǎng)絡(luò)」。

字節(jié)跳動這家公司，應(yīng)該是所有秋招的公司中，對算法最重視的一個了，每次面試基本都會讓你手撕算法，今天這篇文章就記錄下當(dāng)時被問到的幾個算法題，并且每個算法題我都詳細著給出了最優(yōu)解，下面再現(xiàn)當(dāng)時的面試場景?？赐暌欢ㄗ屇阌兴斋@

一、小牛試刀：有效括號

大部分情況下，面試官都會問一個不怎么難的問題，不過你千萬別太開心，因為這道題往往可以拓展出更多有難度的問題，或者一道題看起來很簡單，但是給出最優(yōu)解，確實很不容易的。這道題是這樣的

給定一個只包括 '('，')'的字符串，判斷字符串是否有效。注：空字符串屬于有效字符串

示例 1:
輸入: '(())'
輸出: true

 實例 2：
 輸入: '())('
輸出: false

第一眼看到這道題，我去，這么簡單，穩(wěn)了（因為一面的時候，剛剛被面試官懟過勇者斗惡龍的DP題，在 leetcdoe 屬于 hard 級別）。

其實這道題的 leetcode 第 20 題的簡化版，屬于 easy 級別

于是我也不假思索直接用棧來解決了，相信 99% 都會用棧解決吧？這里我稍微說以下過程吧，步驟如下：

1、在遍歷字符串的過程中，遇到 '(' 就讓它入棧，遇到 ')' 就判斷下棧里面有沒有 '(' ，分以下兩種情況：

（1）、如果有，則把處于棧頂?shù)?'(' 彈出，相當(dāng)于和 ')' 進行匹配，然后繼續(xù)往后遍歷字符串

（2）、如果沒有，則匹配失敗。相當(dāng)于字符串的最前面出現(xiàn)了 ')'，顯然這是不合理的。

2、當(dāng)字符串遍歷完成，判斷棧是否為空，如果為空則表示字符串有效，否則無效。

為了兼顧小白，我該給你們畫了個圖演示，，，，我太良心了。

代碼如下所示（Java，不過不是學(xué)Java也能看懂）

public static boolean isValid(String s){
    if(s == null || s.length() < 1)
        return true;
    int n = s.length();// 字符串長度
    // 創(chuàng)建一個棧來裝字符
    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;
}

二、優(yōu)化

接著面試官說我這道題的空間復(fù)雜度是 O(n)，問我能優(yōu)化一下嗎？

說實話，如果你做過 leetcode 的第 20 題，可能你的腦子會被定向也不一定，因為那道題用棧來處理就是最優(yōu)解的了。不過這道題屬于簡化版，其實可以把空間復(fù)雜度優(yōu)化成 O(1)，大家可以想一下哦。

由于我們棧里面存放的都是**同一種字符 **'(' ，其實我們可以用一個變量來取代棧的，這個變量就記錄 '(' 的個數(shù)，遇到 '(' 變量就加 1，遇到 ')' 變量就減 1，棧為空就相當(dāng)于變量的值為 0。

當(dāng)時腦子有點不知為啥，就馬上相當(dāng)這個方法了，于是一分鐘就修改好了代碼，如下：

public static boolean isValid(String s){
    if(s == null || s.length() < 1)
        return true;
    int n = s.length();// 字符串長度
    // 用來記錄遇到的 '(' 的個數(shù)
    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;
}

這樣子的話，時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。

三、最長有效括號

接著面試官就繼續(xù)就這道題繼續(xù)加大難度，問題改為如下

給定一個只包含 '(' 和 ')' 的字符串，找出最長的包含有效括號的子串的長度。

示例 1:

輸入: '(()'
輸出: 2
解釋: 最長有效括號子串為 '()'
示例 2:

輸入: ')()())'
輸出: 4
解釋: 最長有效括號子串為 '()()'

其實這道題就是 leetcode 的原題，第 32 題，難度為 hard。

這道題由于我之前做過，微微一笑，假裝用嚴肅的表情思考一下，然后馬上給出了思路，剛開始我是用暴力法的。

1、暴力法

暴力法其實很簡單，就是最開始把第一個字符當(dāng)做最長有效括號的首字符來遍歷字符串，接著把第二個字符當(dāng)做最長有效括號的首字符來遍歷字符串，接著把第三個字符……

例如對于 s = '( ) ) ( ( ) )'。

把第一個字符作為首字符，則 max = 2 （遇到第三個字符 ')' 就匹配不了了）
把第二個字符作為首字符，則 max = 0 （一開始就是 ')'，顯然啥也匹配不了）
把第三個字符作為首字符，則 max = 0
把第四個字符作為首字符，則 max = 4
…..
這種做法的時間復(fù)雜度為 O(n^2)，空間復(fù)雜度為 O(1)

基本上面那道題一樣，只是做了 n 次遍歷。

接著面試官問，還能優(yōu)化嗎？

早就知道會問優(yōu)化的了，我自己之前也做過這道題，于是假裝思考了一下，馬上給出了優(yōu)化。

2、優(yōu)化

這道題的優(yōu)化版本我們?nèi)匀皇怯脳碜觯贿^入棧的時候，不是讓 '(' 入棧，而是讓 '(' 的下標入棧。步驟如下：

1、先把 -1 放入棧內(nèi)。（至于為什么？看到后面你就知道了）
2、、對于遇到的每個 '(' ，我們將它的下標放入棧中。
3、對于遇到的每個 ‘)’ ，我們彈出棧頂?shù)脑夭?dāng)前元素的下標與彈出元素下標作差，得出當(dāng)前有效括號字符串的長度。

通過這種方法，我們繼續(xù)計算有效子字符串的長度，并最終返回最長有效子字符串的長度。

看不懂？沒事，我弄個例子畫幾個圖，例如 s = '( ) ) ( ( ) )'，并且用變量 max 來保存最長有效字符串的程度，i 表示當(dāng)前字符串的下標

0、初始化：max = 0; i = 0。-1 放入棧內(nèi)

1、i = 0，s[i] = '('，下標 i = 0 入棧

2、i = 1，s[i] = ')'，出棧; i - 棧頂元素 = 1 - (-1) = 2，此時 max = 2

3、i = 2，s[i] = ')'，出棧；這個時候要注意：由于 -1 出棧后，棧頂沒有元素了，所以這個時候我們必須把 ')' 的下標入棧，相當(dāng)于最開始的初始化。

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、遍歷結(jié)束，最長有效括號為 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;
}

這種做法的時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(n)，能想到用棧來處理，算是很不錯的了。

4、最后一擊

我以為我給出這個解法算是可以的了，面試官應(yīng)該換一道題的了，然后，面試官又來了一句：還能再優(yōu)化嗎？。這個時候我陷入了沉思…….

看文章的各位大佬們可以想一想在空間上是否還能優(yōu)化，因為在時間上是不可能優(yōu)化的了。

想了一會，居然不可以用棧，優(yōu)化的方案肯定是類似于上面那道題一樣，用記錄數(shù)量的變量來代替棧，然后就被我想出了，具體如下：

實際上，這道題仍然可以像上面那樣，用變量來代替棧來優(yōu)化，不過這個時候我們需要兩個變量，我們假設(shè)變量為 left 和 right。

我們在從從左到右遍歷字符串的過程中，用 left 記錄 '(' 的數(shù)量，用 right 記錄 ')' 的數(shù)量。并且在遍歷的過程中：

1、如果 left >= right，顯然這個時候 right 個 ')' 都將一定能夠得到匹配。所以當(dāng)前的有效括號長度為 2 * right。然后更新 max。

2、如果 left < right，顯然這個時候部分 ')' 一定得不到匹配，此時我們把 left 和 right 都置為 0。

當(dāng)遍歷完字符串，我們是否就得到最大長度的有效括號了呢？大家可以想一下

答是不可以的，我們還需要從右到左遍歷計算一下。

為什么呢？

因為實際上 '(' 和 ')' 其實是等價的，為什么就不可以倒過來遍歷計算呢？所以，千萬別忽略了哈。

最后的代碼如下：

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;
}