關於演算法筆試,labuladong 說點套路

語言: CN / TW / HK

我知道各位是被標題吸引進來的,那就不廢話,先說幾個演算法筆試的硬核套路,再說說做題複習的策略。

避實就虛

大家也知道,大部分筆試題目都需要你自己來處理輸入資料,然後讓程式列印輸出。判題的底層原理是,把你程式的輸出用 Linux 重定向符 > 寫到檔案裡面,然後比較你的輸出和正確答案是否相同。

那麼有的問題難點就變得形同虛設,我們可以偷工減料,舉個簡化的例子,假設題目說給你輸入一串用空格分隔的字元,告訴你這代表一個單鏈表,請你把這個單鏈表翻轉,並且強調,一定要把輸入的數字轉化成單鏈表之後再翻轉哦!

那你怎麼做?真就自己定義一個 ListNode 單鏈表節點類,然後再寫程式碼把輸入轉化成一個單鏈表,然後再用讓人頭暈的指標操作去老老實實翻轉單鏈表?

搞清楚我們是來 AC 題目的,不是來學習演算法思維的。正確的做法是直接把輸入存到數組裡,然後用 雙指標技巧 幾行程式碼給它翻轉了,然後打印出來完事兒。

我就見過不少這種題目,比如題目說輸入的是一個單鏈表,讓我分組翻轉連結串列,而且還特別強調要用遞迴實現,就是我們舊文 K 個一組翻轉連結串列 的演算法。嗯,如果用陣列進行翻轉,兩分鐘就寫出來了,嘿嘿。

還有我們前文 扁平化巢狀列表 講到的題目,思路很巧妙,但是在筆試中遇到時,輸入是一個形如 [1,[4,[6]]] 的字串,那直接用正則表示式把數字抽出來,就是一個扁平化的列表了……

巧用隨機數

再說一個雞賊的技巧,注意那些輸出為「二值」的題目,二值就是類似布林值,或者 0 和 1 這種組合有限的。

比如說很多題目是這樣,巴拉巴拉給你說一堆條件,然後問你輸入的資料能不能達成這些條件,如果能的話請輸出 YES,不能的話輸出 NO

如果你會做當然好,如果不會做怎麼辦?

首先這樣提交一下:

public class Main {
    public static void main(String[] args) {
        System.out.println("YES");
    }
}

看下 case 通過率,假設是 60%,那麼說明結果為 YES 有 60% 的概率,所以可以這樣寫程式碼:

public class Main {
    public static void main(String[] args) {
        // 60% 的概率輸出 YES,40% 的概率輸出 NO
        System.out.println((new Random().nextInt() % 100) < 60 ? "YES" : "NO");
    }
}

嘿嘿,labuladong 說了,這題你可以不會,但是一定要在力所能及的範圍內做到極致!

概率大師

說一個場景,如果筆試出現那種噁心人的單選,四個選項全都沒見過,然後你蒙了一個 C。

假設,過了一會你突然靈光一閃,喚起一些零碎的記憶,確定 B 選項是錯的,那麼,這時候你該怎麼做?

重新在 A 和 D 中間蒙一個啊哥哥!不重新蒙,正確的概率是 1/4,重新蒙,正確的概率是 3/8,白撿的概率都不要麼?

是不是覺得不可思議?是不是覺得我在胡扯?

這樣,假設一道選擇題有 100 個選項,你隨便蒙一個,正確率為 1%,錯誤率為 99%。

假設現在 labuladong 顯靈,幫你在剩下的 99 個選項中排除了 98 個錯誤選項,只剩下一個選項,然後問你,你繼續堅持原來的選擇,還是換成幫你排除剩下的那個選項?

換啊!換了之後正確概率是 1 - 1% = 99% 啊!

那如果 labuladong 只幫你排除了 90 個錯誤選項,剩下 9 個選項,那你要不要換成這 9 個選項中的某一個?

換啊!換了之後正確概率是 (1 - 1%) / 9 = 11% 啊!

那回過來看,四個選項,你開始蒙了一個,後來靈光一閃在剩下三個選項中排除了一個錯誤答案,那你換不換?

換啊!換了之後正確概率是 (1 - 1/4) / 2 = 3/8 啊!

其實這就是典型的「三門問題」,不知道的話看舊文 幾個反直覺的概率問題

程式語言的選擇

僅從做演算法題的角度來說,我個人比較建議使用 Java 作為筆試的程式語言。因為 JetBrain 家的 IntelliJ 實在是太香了,相比其他語言的編輯器,不僅有 psvm 和 sout 這樣的快捷命令(你要是連這都不知道,趕緊面壁去),而且可以幫你檢查出很多筆誤,比如說 while 迴圈裡面忘記遞增變數,或者 return 語句錯寫到迴圈裡這種由於疏忽所導致的問題。

C++ 也還行,但是我覺得沒有 Java 好用。我印象中 C++ 連個分割字串的 split 函式都沒有,光這點我就不想用 C++ 了……

還有一點,C++ 程式碼對時間的限制高,別的語言時間限制 4000ms,C++ 限制 2000ms,我覺得挺吃虧的。怪不得看別人用 C++ 寫演算法,為了提高速度,都不用標準庫的 vector 容器,非要用原始的 int[] 陣列,我看著都頭疼。

Python 的話我刷題用的比較少,因為我不太喜歡用動態語言,不好除錯。不過這個語言的奇技淫巧太多,如果你深諳 Python 的套路,可以在某些時候投機取巧。比如說我們前文寫到的 表示式求值演算法 是一個困難級別的演算法,但如果用 Python 內建的 exec 函式,直接就能算出答案。

這個在筆試裡肯定是很佔便宜的,因為之前說了,我們要的是結果,沒人在乎你是怎麼得到結果的。

解法程式碼分層

程式碼分層應該算是一種比較好的習慣,可以增加寫程式碼的速度和降低除錯的難度。

簡單說就是,不要把所有程式碼都寫在 main 函式裡面,我一直使用的套路是,main 函式負責接收資料,加一個 solution 函式負責統一處理資料和輸出答案,然後再用諸如 backtrack 這樣一個函式處理具體的演算法邏輯。

舉個例子,比如說一道題,我決定用帶備忘錄的動態規劃求解,程式碼的大致結構是這樣:

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 主要負責接收資料
        int N = scanner.nextInt();
        int[][] orders = new int[N][2];
        for (int i = 0; i < N; i++) {
            orders[i][0] = scanner.nextInt();
            orders[i][1] = scanner.nextInt();
        }
        // 委託 solution 進行求解
        solution(orders);
    }

    static void solution(int[][] orders) {
        // 排除一些基本的邊界情況
        if (orders.length == 0) {
            System.out.println("None");
            return;
        }
        // 委託 dp 函式執行具體的演算法邏輯
        int res = dp(orders, 0);
        // 負責輸出結果
        System.out.println(res);
    }

    // 備忘錄
    static HashMap<String, Integer> memo = new HashMap<>();
    static int dp(int[][] orders, int start) {
        // 具體的演算法邏輯
    }
}

你看這樣分層是不是很清楚,每個函式都有自己主要負責的任務,如果哪裡出了問題,你也容易 debug。

倒不是說要把程式碼寫得多規範,至於 private 這種約束免了也無妨,變數用拼音命名也 OK,關鍵是別把程式碼直接全寫到 main 函式裡面,真的亂,不出錯也罷,一旦出錯,估計要花一番功夫除錯了,找不到問題亂了陣腳,那是要儘量避免的。

考前複習策略

考前就別和某一道演算法題死磕了,不划算。

應該儘可能多的看各種各樣的題目,思考五分鐘,想不出來解法的話直接看別人的答案。看懂思路就行了,甚至自己寫一遍都沒必要,因為比較浪費時間。

筆試的時候最怕的是沒思路,所以把各種題型都過目一下,起碼心裡不會慌,只要有思路,平均一道題二三十分鐘搞定還是不難的。

前面不是說了麼,沒有什麼問題是暴力窮舉解決不了的,直接用 回溯演算法套路框架 硬上,大不了加個備忘錄,不就成 動態規劃套路框架 了麼,再大不了這題我不做了麼,暴力過上 60% 的 case 也挺 OK 的。

別的不多說了,套路這個東西,說來簡單,一點就透,但問題是不點就不透。本文我簡單介紹了幾個筆試演算法的技巧,各位好好品味~

PS:我認真寫了 100 多篇題解,手把手帶你刷力扣,持續更新,全部發布在 我的GitBook,建議收藏,幫助大家學習演算法~