演算法小白如何高效刷LeetCode?

語言: CN / TW / HK

心理建設篇

在講述具體的方法之前,先要明白一件事。凡事都分『道』與『術』。本問題下面大部分回答介紹的都是『術』。而對於刷LeetCode這件事,無論你看到多少高明的的方法,如果你不能持之以恆,都沒有用。所有在刷LeetCode這件事上,他的『道』就是:如何能持之以恆的保持刷題熱情。我認為『道』更重要。我先談一下這部分。

尋找標尺,讓進步可衡量

為什麼王者榮耀有段位,有青銅、白銀、黃金。以我個人的經驗來看,這些都是刺激你持續玩遊戲的遊戲機制。通過段位,彰顯個人的實力,沒錯,裝逼是人類進步的一大動力。同時也讓進步可以衡量。刷LeetCode也是同樣,一般剛開始我們會關注解決了多少道題。更進一步,我們需要關心自己的排名。LeetCode也有排名機制。每刷一道題,就前進一點點。可以每週給自己做一個記錄,記一下自己的排名。讓自己重視排名。逐漸的自己就會把積極性調動起來,想讓自己的排名越來越高,就是打排位一樣。

除了排名,你還可以每週記錄一下 通過率。

尋找小驚喜,給自己正反饋

堅持做每日一題,LeetCode每天都有一道題,完成後,你的打卡日曆就會勾上一個圈。

如果打滿一個月就會獲得一個月度徽章。另外LeetCode有很多“學習計劃”,每個學習計劃完成後也會有一個徽章。

我有段時間就喜歡收集徽章,為了收集這些小玩意,會刺激自己持續解題。其實和遊戲裡面也差不多。學會遊戲化學習。

不要死磕,學會放棄

開始刷LeetCode感到吃力是正常的。我這裡說的學會放棄,不是說放棄刷力扣,而是說碰到自己無法解決的題目,不要死磕。趕緊看一下題解去學習,這沒有什麼丟人的。每個人都是從這個階段過來的。就比如小學生無法做出高中生的題目,並不是因為小學生笨,而是因為中間有很多知識,小學生沒學過。對於演算法而言,自然也是如此。靠自己死磕,是很難想到很多前輩科學家們總結出來的演算法。這時候去看題解學習也不為過。

如果遇到特別難的題,看題解也不理解。也不用糾結。就隔著它。可以把題號記下來。過段時間再回顧。

好記性不如爛筆頭

我是筆記強迫症患者……我現在刷LeetCode,每道做過的題,我都會記到Notion裡。打上幾個標籤,方便回顧。

記憶是有遺忘曲線的,不能因為你現在能做出一道題,就認為自己能永遠做出來。小學時,老師就教導我們:

好記性不如爛筆頭

講完『道』,我也談一下我的『術』。我這裡不對具體的演算法和資料結構題型做解析了,我主要給你指路。

我伸手給你指路,希望你看見的是路,而不是我的手

刷題順序篇

當然我不建議從頭按順序刷,我分為“正排”刷題和“倒排”刷題,兩種策略。

所謂“正排刷題”可以刷LeetCode上面的題單。

我個人建議從《劍指Offer》開始刷。《劍指Offer》現有出了兩冊,在LeetCode上都有題單。建議從《劍指Offer》刷起,碰到不會的,可以看書中的講解。

根據書來刷題,當你刷完一本書後,常見的題目型別幾乎都覆蓋到了。當然同一種類型的題目數不勝數,重要是培養一下各種題型大概的思路。這屬於“正排”刷題。

“倒排”刷題,是打破常規,不根據題目型別或按照某種順序來做題。玩的就是措手不及。比如堅持做 每日一題 。堅持一個月你就會見到各種各樣的題型,有的甚至很刁鑽。方便查漏補缺。另外如果有信心的話,可以參加一下週賽,進一步給自己驚喜。

網站/APP使用篇

自定義測試用例

不要著急提交程式碼。多用測試用例自測。如果是提交之後發現某個case不過,除錯的時候一定要在測試用例這裡除錯。

不要用重複提交程式碼的方式除錯。每次提交程式碼都會跑N多個case,時間慢。另外就是會降低你在LeetCode上的“通過率”

高效安排刷題時間

如果你是學生,那麼恭喜你有一大把的時間用來刷題。但是如果你是已工作人士,則需要高效利用時間了。由於我經常做每日一題,而每日一題,是零點更新。有時候躺在床上沒睡,就用力扣APP開啟看一眼題目,如果題目不難,就直接用APP刷了。另外你也可以利用上下班通勤的時間、出去玩乘坐地鐵、公交的時間來用手機看看題解,或者直接用手機刷。比如我坐長途車從家裡回北京的路上就用手機刷過題。

手機刷題,其實官方APP,有很多程式語言中的特殊符號的候選功能,可以加快不少手機輸入的速度。

另外你可以給你的輸入法用自定義,加入一些常用的程式碼,進一步提高手機輸入的效率。

Trick篇

修改函式引數

leetcode的引數名,有時候很長,你可以改名字,減少輸入的字元數。當然正常在網站上刷題有補全功能。但是改一下名字,還是簡化不少。另外就是有兩個例外情況是沒有補全的:

  1. 手機刷題(力扣手機APP可以刷題,但是沒有補全功能)

  2. 參加周賽(周賽IDE,無自動補全功能)

呼叫待補全函式自身

如果函式的引數是等價的,但是你根據某種策略,把他們分出來差別。但是你不確定哪個引數是滿足的。比如這道:

415. 字串相加

https://leetcode-cn.com/problems/add-strings

官方給出的程式碼是這樣:

class Solution {
public:
string addStrings(string num1, string num2) {

}
};

num1和num2在題目中含義是等價的。但是我們希望以長度長的那個num作為base,來疊加長度短的那個num。這樣可以方便處理。你可以直接去判斷長度,然後再搞兩個變量出來。比如:

auto& base = num1.size() > num2.size() ? num1: num2;
auto& delta = &base == &num1 ? num2 : num1;

然後讓base再去加delta。。但其實沒必要這麼麻煩,直接這樣:

class Solution {
public:
string addStrings(string num1, string num2) {
if (num1.size() < num2.size()) {
return addStrings(num2, num1); // 呼叫自身
}
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
// num1長度 肯定大於等於num2
stringstream ss;
int c = 0;
for (int i = 0; i < num1.size(); ++i) {
int x = num1[i] - '0';
int y = i < num2.size() ? num2[i] - '0' : 0;
int n = x + y + c;
int d = n%10;
ss<<d;
c = n/10;
}
if (c) {
ss << c;
}
string s = ss.str();
reverse(s.begin(), s.end());
return s;
}
};

給解題函式增加預設值

每道題,LeetCode都會給出一個待補全的函式,這個函式,你是可以增加預設值的。

對於某些遞迴的解法,可以少定義一個函式.

官方庫提升刷題效率(C++)

因為我是C++程式設計師所以下面就只介紹C++了。

記住一定要學好STL!

swap替代手寫交換

不要在自己寫三行式去寫交換了。直接用swap。

針對連結串列的Node也使用哦。比如:

226. 翻轉二叉樹:

https://leetcode-cn.com/problems/invert-binary-tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (!root) {
return root;
}

swap(root->left, root->right);

mirrorTree(root->left);
mirrorTree(root->right);

return root;
}
};

pair替代二元資料結構

有時候我們可能需要一些臨時的資料結構。如果這個資料結構只有兩個成員變數,那麼你大可不必定義出來一個struct或class。直接上pair!比如這道:

38. 外觀數列

https://leetcode-cn.com/problems/count-and-say
class Solution {
public:
string countAndSay(int n) {
string num = "1";
for (int i = 1; i < n; ++i) {
auto s = say(num);
num.swap(s);
}
return num;
}
string say(const string& num) {
vector<pair<char, int>> v; // 直接用pair
v.emplace_back(num[0], 1);
for (int i = 1; i < num.size(); ++i) {
if (v.back().first == num[i]) {
v.back().second++;
} else {
v.emplace_back(num[i], 1); // pair對emplace友好
}
}

stringstream ss;
for (auto& pa: v) {
ss<<pa.second<<pa.first-'0';
}
return ss.str();
}
};

pair還有其他好處,那就是它自帶 operator< 比較運算子。如果你的自定義型別需要排序的話,那麼pair就不需要你自己寫這個比較函數了。而自定義型別則需要。

而且pair的建構函式可以直接接受first和second的值做引數。這對於 emplace 或者 emplace_back 都很友好!

accumulate()求陣列的和

int sum = accumulate(nums.begin(), nums.end(), 0);

partial_sum()部分求和

對於某些 字首和 相關的題目,可以簡化程式碼

    vector<int> v = {1,2,3,5,6,7};
vector<int> pre;
partial_sum(v.begin(), v.end(), back_inserter(pre));
for (int i: pre) {
cout<< i<<endl;
}

輸出:

min()和max()

比如我們一般怎麼求最小值呢?

if (v[i][t] < v[f][t-1] + price) {
v[i][t] = v[f][t-1] + price;
}

可以直接用std::min()來簡化if else:

v[i][t] = min(v[i][t], v[f][t-1] + price)

工作中不太需要,刷題適合。如果你需要從三個數字中求最小值呢?加一層{}

val = min({a, b, c});

如果求最大值就用std::max()

max_element()和min_element()

如果要從一個數組中找出最大值呢?

一般我們可能這麼寫:

int val = -1; // 假設-1是肯定小於dp[i]的
for (int& v: dp) { // dp是vector<int> 型別
if (v > val) {
v = val;
}
}
return val;

太長了,可以直接:

return *max_element(dp.begin(), dp.end()); // 這樣寫的前提是能保證dp不是空的,否則段錯誤!

二分查詢相關

upper_bound()lower_bound() 有時可以直接拿來解二分法相關的題目,避免自己手寫出錯。

往期推薦

從旁觀者到committer,我與brpc的故事
大四那一年
C/C++:堆疊面面觀
過往工作中的一些趣事