初見 LeetCode,演算法心得
Alpha Came 的全端課程告了一個段落,差不多到了該準備求職的時候。
聽說工程師的面試,有些公司會有一種叫做白板題的玩意,考你一些演算法,並要求當場在白板上解題。
會要求在白板上現場解,而不是像傳統考試一般,發一張考卷,給予一段時間自己解題最後對答案。可以推測出這類關卡企圖檢驗的應該不是單純的解題力,而是希望看看這個人的溝通能力,以及邏輯思路大概如何。
但不管如何,毫無準備就直接面對這樣的面試關卡,當下腦袋一定會跟那面白板一樣的白,所以適當的練習與準備還是必要的。於是這邊就來試試大多人會推薦的 LeetCode 來練習演算法。
這個網站似乎是蒐集了各式各樣的演算題,以及各大公司的考古題來給大家練習。當然,也支援各種不同語言。
這邊練習了 Alpha Camp 課程篩選出的 10 題 Easy 入門題,實在相當有趣,於是想稍微分享一些心得。
何謂演算法 ( algorithm)
相信很多想轉職工程師的人應該也跟我一樣,第一次看到演算法這三個字整個就矇了,光看字面就覺得超級難。
但學了一陣子之後發現,程式領域很多都是術語看起來超難,本質上卻只是把很簡單的概念故意取一個很高大尚的名子。就像很多料理名稱一樣,什麼「螞蟻上樹」等等,名子看起來很有學問,其實只是粉絲炒肉。
「演算法」本質上只是在說「命令電腦幫人做事」的方法。所以也有人會稱呼為「寫(商業)邏輯」。而這個過程就很像是一個便利商店的老闆,寫了一份員工訓練手冊,去教新來的工讀生如何幫客人結帳。演算法只是將那份手冊,改寫成電腦看得懂的「程式語言」,藉此要求電腦幫你結帳。
而電腦運作方式畢竟不像人腦,無法處理「模糊命令」。所以必須要很有邏輯的條列出各種狀況應該怎麼做,電腦才有辦法執行。而這部份就會變得很像在算數學題,所以稱為演算法。
個人感覺,演算法跟數學競試一樣,可以粗分成兩大類型:
1. 純計算類,單純考驗 Array、String 之類的操作熟練度。
2. 邏輯類,考驗「找規律」的能力,針對規律去研究解決方案。
邏輯能力可能是比較重要的一環,畢竟計算問題,可以 Google 找公式、找套件,也可以花時間自己慢慢算。但邏輯能力缺乏的情況,就比較難救了。
LeetCode 的題目,涵蓋了計算題、邏輯題、綜合性題。自己寫個 10 題的感想,就算沒打算要當工程師,這也是個打發時間的好東西,更可以防老年癡呆 (笑)。
緊接著,這邊稍微分享一些,自己在刷題時注意到的點。
有 Solution 可以參考
有些題目,在左上方是有 Solution 可以看的。裡面不只寫出解法,還有說明背後的邏輯。有許多題目更會提供 2~3 種不同思路的解法,自己解完一次之後,再去看其他的解法,可以學到相當多東西。
只是全英文稍微痛苦了一點,而且沒有提供全語言的解法,而是 Java、C++、Python 這三種的解比較多。但高階語言的語意化都做得相對好些,有些時候即使不會那個語言,也是能猜出做了些甚麼,但 C++ 的個人是真的比較看不懂。
有 Discuss 可以參考
除了 Solution 之外,也有討論版可以查看大佬們提供的解法。這邊可以利用 Tag 去搜尋自己會的語言來看別人的解法。除了主思路以外,還能看到「同樣思路」的各種花式寫法,時不時可以看到一些自己根本不知道的 method,或是很潮的 one-line 解。這可以大幅提升自己在寫法上的技術力。
但要稍微注意一下,有些是「放棄易讀性」的寫法,這類寫法在正式工作時最好別用,不然會增加其他人 Review 的困難度。
Runtime 計算耗時
LeetCode 會去計算花費時間,並且列出一個競速 Rank 排行。這雖然可以刺激出競爭慾,但多搓幾次會發現,相同的寫法每次 Submit 花費時間都是有落差的,甚至早上跟晚上 Submit 速度差異也蠻大的。所以不要太盲目的去追求 Runtime 速度會比較健康 (?)。
以 JavaScript 的情況,for 遍歷鐵定是比陣列方法 forEach 快很多的,但我個人比較常用 forEach,因為 forEach 個人覺得比較易讀,由於是調用匿名 function,所以可以使用 if return 的寫法,來拆除 if else 的巢狀結構。
但是為了追速度,而改用比較不習慣的 for 迴圈,反而意外的練習到平常不太用的寫法。
部分陣列題會要求 in-place
第一次看到 in-place 其實不太理解是什麼意思。後來查了一下,似乎是說要在「原地計算」。例如陣列的情況,就是要求不建立輔助陣列,就地操作原陣列完成目標,但可以建立輔助變數。
個人除了 sort 之外,鮮少這樣操作陣列,畢竟新建一個陣列,把要的東西找出來放進去,又直覺又簡單。為了完成 in-place 的要求,反而得知了一些操作陣列的神奇技術。但未來實作能否用上就不清楚了,因為有些操作方式真的很不直覺,除非刻意去背過、練過,不然臨場真的很難會想到。
輔助用變數很像人類在記 memo
這是刷了幾題之後,突然領悟 (?) 到的。例如現在有一個陣列 [1, 1, 1, 2, 2],要去算有幾個 1、幾個 2。人類的做法會是會在腦中去記有幾個,或是扳手指去數,也可以寫個正字記在紙上。
這樣的動作,其實就跟寫 Code 在迴圈前面設個輔助變數是一樣的邏輯。
let count = 0 // 這行就如同人類記 memo
for (const num of nums) {
if (滿足條件) { count += 1 }
}
很多題目會需要用到這樣的思路,其中比較有趣的應用,是用 Object 來計數。
const count = {};
[1, 1, 1, 2, 2].forEach(num => {
if (!count[num]) return count[num] = 1
count[num] += 1
})
console.log(count) // { "1": 3, "2": 2}
小技巧,逆向遍歷防跳號
有些陣列操作的題目,需要找出符合條件者,將其移動位置或是移出陣列。這類題目應該多數人的直覺都會是,直接 each 然後寫 if 就完事了,結果解題失敗。
這是因為 each 會照 index 順序,逐一掃瞄陣列。如果中途將某個 value 抽換掉,會導致陣列 size 發生改變,each 就會出現跳號的邏輯 bug。後來看討論區,發現逆向遍歷即可解決,真是太神奇了 (笑)。
// 逆方向遍歷
for (let i = (nums.length - 1); i >= 0; i--) {
if (符合條件) { nums.splice(i, 1) }
}
神奇的位元運算子 「& (AND)」、「| (OR)」、「^ (XOR)」
我想這個應該非工程科系出生的,可能根本不知道有這種種西。剛開始學程式沒多久,應該就會學到邏輯運算子:
a && b; // a AND b
a || b; // a OR b
但不知道大家有沒有好奇過,為何是兩個「&」與兩個「|」呢?這是因為,單個符號的情況下,代表別種計算,也就是「位元運算子」。
這玩意一樣是 AND、OR 那些算法,只是它比較的東西是二進位的 0 跟 1,根據比較條件返回 0 或 1,這是屬於比較計算機科學的概念。
而這種計算有一些神奇應用,例如可以快速判斷奇偶數,任一數與 1 做 & 比較,結果為 1 者必為奇數,為 0 者必為偶數。原理我這邊不多贅述,Google 有很多前輩介紹過。
21 & 1 // 1, 奇數
44 & 1 // 0, 偶數
另一個比較神奇的是 XOR 運算子,它只有 0 跟 0 或是 1 跟 1 比較時,才會返回 1,位元數不一樣,則返回 0。
這會產生一個特性,就是某數 num 跟 a 做比較之後會生成一個新的數,再跟 a 比較又會變回 num,所以可以當作加解密的工具。
const key = 3
5 ^ key // 6, 會變成啥無法預測,達到加密效果
6 ^ key // 5, 再跟 key 比一次會還原,達到解密效果
而這個神奇的特性,剛好可以用來解 LeetCode 第 136 題 Single Number。這題給定一個整數 Array,例如 [4, 1, 2, 1, 2],並要求找出唯一存在的數。
此題就可以利用 XOR 運算的特性,兩個相同的數撞在一起會抵消,最後只會剩下 Single Number。
var singleNumber = function (nums) {
for (let i = 1; i < nums.length; i++) {
nums[0] ^= nums[i]; // 做 XOR 運算並賦予,撞到一樣的數會還原抵銷
}
return nums[0]; // 最後剩下的數為 Single Number
};
可以看到自己沒學過的「經典演算法」
多看討論區跟解答區,有些題目可以看到一些經典問題。既然是經典問題,自然會有那種大佬們吸收日月精華後發表的針對性解法。
例如 Alpha Camp 課程裡面,就曾提到過一種 Fisher–Yates shuffle (洗牌演算法),可以用來寫尾牙抽獎箱,摸彩卷票號這類玩意。
LeetCode 自然也會出現這類經典問題,例如第 169 題 Majority Element。這題給定一個整數 Array,例如 [3, 2, 3],要求找出數量最多的數字。這種題目非常的像「多數決投票」的場景,屬於經典問題。
所以討論區也可以看到一種叫做 Boyer-Moore Voting Algorithm (多數投票算法) 的玩意。它的原理還蠻妙的,真的花了一陣子才看懂。作法上大概是這樣:
- 開出第一票時,將此候選人紀錄下來,並登記 1 票。
let name = '候選人A'
let count = 1
2. 之後開票,只要是他就 +1,不是就 -1
3. 減到票數為 0 時,把當前票的候選人名換上去,然後票數 +1
name = '候選人B'
count = 1
4. 這樣算到最後,板子上的名子就是票數最多者
寫成 Code,大概是這種感覺:
var majorityElement = function(nums) {
let count = 0
let result = 0
for (const num of nums) {
if (count === 0) { result = num }
count += (num === result ? 1 : -1)
}
return result
};
這種經典演算法真的非常的神奇,真覺得想出來的人大腦結構一定跟我不一樣 (笑)。