初見 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. 開出第一票時，將此候選人紀錄下來，並登記 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
};

這種經典演算法真的非常的神奇，真覺得想出來的人大腦結構一定跟我不一樣 (笑)。