[課程學習筆記 ]先別急著寫 leetcode — 一步步打造程式腦

課程說明：https://github.com/Lidemy/ALG101-too-weak-to-leetcode
課程連結：https://lidemy.com/p/alg101-leetcode

寫程式不等於寫程式碼

初學者寫程式

1. 邊寫程式碼邊想怎麼解
2. 試著套用自己以前學過的語法

會寫程式的人寫程式

1. 會先想解法，在腦中構思（只是太快看不出來）
2. 把解法轉換成程式碼

兩者的差異就在於是否有整理過自己的想法，讓想法變的清晰，並且是可表達的，即便不懂任何的程式語言也可以「寫程式」。

因此這篇是整理在寫程式之前可以先練習的事情。

在寫程式之前，先學會 pseudo code（虛擬碼）

打造工程腦的第一步：在寫程式之前，先想好怎麼做

打造工程腦的第一步：想解法

想解法這件事有點抽象，最常見的狀況是「想得出來但不知道如何轉換程式碼」。

舉個例子，請印出 1~100 之間的偶數，

我們解的出來嗎？可以，答案是 2,4,6,8….100，那實際步驟是怎麼做呢？

因此更好的方法是將把想法變成「寫出一行行的可執行步驟」而要訣在於

1. 大問題分割成小問題
2. 一行只做一件事情
3. 善用跳轉（jump）來實現重複執行
4. 善用條件判斷

實際運用：印出 1~100 之間的偶數

我們先將問題進行切割成「印出 1~100」及「偶數」

Q1：如何印出 1~100

1. 令 i = 1
2. 如果 i > 100，結束
3. 印出 i
4. i = i + 1
5. 跳回第二行

Q2：如何找出 「偶數」

偶數 = 能被 2 整除

1. 令 i = 1
2. 如果 i > 100，結束
3. 如果 i 能被 2 整除，印出 i
4. i = i + 1
5. 跳回第二行

這樣就成功將把想法變成「寫出一行行的可執行步驟」。

打造工程腦的第二步： pseudo code（虛擬碼）

pseudo code 是程式碼跟你的想法之間的橋樑，把解法用抽象的方式去表示，長得非常像程式碼！

我們可以將剛剛的可執行步驟翻成英文

1. let i = 1
2. if i > 100, then exit
3. if i % 2 no remainder, print i
4. i = i + 1
5. jump to line 2

再變成 pseudo code

1. let i = 1
2. for (i from 1 to 100) do
3. if i / 2 no remainder, print i
4. end for

假設變成程式碼的話（以 JavaScript 為例）

for(let i = 1; i <= 100; i++) {
  if(i%2 === 0) {
   console.log(i)
   }
}

在寫程式之前，先學會「看程式」

某一次的英文閱讀測驗，老師請小明將測驗文章念一遍，小明非常緊張的看著文章念完，接著老師就問了小明文章題目，但小明一題都回答不出來，因為在唸的當下太緊張了，小明完全沒有理解文章內容，真的只有把看著文章的一個一個字念出來而已。

看程式 ＝ 理解程式碼如何運作

在初學過程中密密麻麻的程式碼很難好好的去看懂，就會變成去硬記在這個情境我可以使用這個方法去解題，無法舉一反三，因此我們可以把自己想像成機器一行一行的去讀取，作為人體翻譯機去翻譯程式碼

人體翻譯機

• 翻譯虛擬碼

let sum = 0
let arr = [1, 2, 3]
for( i from 0 to n-1 ) do
   sum += arr[i]
end for
print sum

1. 令總和為 sum ，sum = 0
2. 令一個陣列為 [1, 2, 3]
3. 讓 i 從 0 跑到 2 （n 通常指的是長度）
4. i 現在是 0
5. sum += arr[0]，sum 等於 1
6. 下一圈迴圈
7. i 現在是 1
8. sum += arr[1]，sum 等於 1 + 2 = 3
9. 下一圈迴圈
10. i 現在是 2
11. sum += arr[2]，sum 等於 3 + 3 = 6
12. 下一圈迴圈
13. i 現在是 3，超出，n-1，結束
14. 輸出 sum

短短幾行字其實做了很多次相同的事情

接著試著翻譯真的程式碼

• 翻譯真的程式碼

let arr = [2, 6, 3];
let max = -Infinity;
for(let i = 0; i < arr.length; i++) {
  if(arr[i] > max) {
      max = arr[i];
   }
}
console.log(max);

1. 假設 arr 為 [2, 6, 3]
2. 令 max 為 arr[0]，也就是 2
3. 設定 i = 0；判斷 i < 3；是，進入迴圈
4. arr[0] 為 2，判斷 arr[0] > -Infinity，是
5. max 等於 arr[0]，現在 max 為 2
6. i + 1
7. 下一迴圈
8. 現在 i 為 1，判斷 i < 3；是，進入迴圈
9. arr[1] 為 6 判斷 arr[1] > 2，是
10. max 等於 arr[1]，現在 max 為 6
11. i + 1
12. 下一迴圈
13. 現在 i 為 2，判斷 i < 3；是，進入迴圈
14. arr[2] 為 3，判斷 arr[2] > 6，不是
15. i + 1
16. 下一迴圈
17. 現在 i 為 3，判斷 i < 3；不是，結束迴圈
18. 輸出 max

寫完覺得…很累，不過確實這訓練的過程讓自己能慢慢的靜下來好好的讀懂每一行 code

其他看程式碼執行的方式

• Debug 神器：Debugger

Chrome Devtool debugger 是一個非常好用的工具，就是讓我們可以查看程式碼執行的工具，可以知道在底層的編譯器眼中程式碼是如何運作的

前置作業：

1. 新增一個 debugger.html 檔案
2. 內容放上剛剛的 找最大值程式碼（記得用 script 包住）
3. <script> 下方增加 debugger

<script>
debugger
let arr = [2, 6, 3];
let max = arr[0];
for(let i = 0; i < arr.length; i++) {
   if(arr[i] > max) {
      max = arr[i];
   }
}
console.log(max);
</script>

4. 用 chrome 開啟 debugger.html 檔案

5. 進入 debug 模式

就可以模擬程式運作的過程囉

詳細的教學可參考：六角學院 — Chrome 網頁除錯功能大解密（免費課程）

• Log

另一個 debug 的方法，加 log 加好加滿。

因為 debugger 會一行一行執行，想要快速的話也快不起來，

有時候只是想知道每個時間點的值，就會比較不方便。

<script>
let arr = [2, 6, 3];
let max = arr[0];
console.log('defult max:', max)
for(let i = 0; i < arr.length; i++) {
   console.log(i,'max:', max);
   if(arr[i] > max) {
      console.log(i,'arr[i]:', arr[i] ,'old max:', max)
      max = arr[i];
      console.log(i,'new max:', max)
   }
}
console.log('last max:',max);
</script>

前面數字為迴圈的圈數

透過 log 就可以清楚知道每個階段的值

補充說明：為什麼我 log 出來怪怪的

請參考以下程式碼

<script>
let arr = [2, 6, 3];
let max = arr[0];
console.log(arr) //[2, 6, 3]
for(let i = 0; i < arr.length; i++) {
   if(arr[i] > max) {
      max = arr[i];
   }
}
arr.push(100) //[2, 6, 3, 100]
console.log(max);
</script>

註解為認為的 log

但點開 arr 的詳細資訊

裡面有四個！

更糟糕的是在未開啟 devTool 重新整理後，連顯示都會變成 4 個。

這個原因在於 log 時間點問題，不管是點開還是開啟 devTool 都是抓取當下時間點的 log

並不是當時的 log

這個問題會出現在「陣列」 跟 「物件」 的時候

因此解決辦法就是將「陣列」 跟 「物件」轉成字串 ＃JSON.stringfy()

寫程式前的最後一步：看懂題目

考驗程式能力前，你真的知道我在問什麼嗎

因為我們正處於資訊爆炸的年代，手機滑呀滑，每天接收的資訊量好幾千則，但說實話記得幾個？為了讓我們能更加記住資訊，標題要聳動，資訊量越短越好，導致我們的閱讀能力逐漸下降。

扯得有點遠，因為我自己超級有感觸的，只要看 1000 字的內容，每個字都像在飛一樣。

看懂題目之練習 ：LIOJ 1008 幾個水桶

輸入範圍很重要

參考題目：LIOJ 1004 聯誼順序比大小

因為不同的規模有不同的思考方式也考量不同的解法

比如說蓋一般大樓跟蓋 101 蓋的方式一定不一樣，規模越大，要考量的點就越多，防震機制、逃生機制、電梯數量與承受壓力等都需要思考。

不同範圍 = 不同限制

以下說明程式解題常碰到的限制

• 空間限制（儲存容量）

如果語言的數字有分型態的話，大約會是以下的容量

1. int（整數）: 4bytes
2. double（浮點數的一種）: 8bytes
3. JavaScript 中的 number ： 8 bytes ＃JavaScript 中數字的型態只有 number 一種。

補充說明
1 Byte = 8 Bits
1 Kilobyte (KB) = 1024 Bytes
1 Megabyte (MB) = 1024 KB
1 Gigabyte (GB) = 1024 MB
1 Terabyte (TB) = 1024 GB
參考資料：儲存容量單位：Bit, Byte, KB, MB, GB, TB , PB, EB, ZB, YB

這邊以 JavaScript 做解釋，如果用到一百萬個數字的話

8* 1e6 /1024 = 781200 KB = 7.6 MB #1e6 = 1 後面跟著 6 個零是一種科學符號表示法。

需要用到 7.6 MB 的記憶體。

但用到十億個數字！

8* 1e8 /1024 = 781200 KB = 7600 MB = 7.4 GB

就必須要有 7.4 GB 的記憶體，這是不太可能的。

範圍決定方法

排序十萬的數字，可以全部載入到記憶體，但如果要排十億的數字，就沒有辦法這樣做了，因為記憶體的空間不夠，就必須另尋方法，比如說，把排好的一部份先放入檔案中等。

• 時間限制（效能）

對於初學來說效能不是太重要，先求有再求好，待以後學習到一些簡單的演算法後，就可以利用在解題中提升效能。

範圍決定方法

排序一百萬個數字跟排序十個數字，效能就會有差。

• 型態限制

有限的整數

意思是只要超過範圍，就代表會產生溢位例外（overflow exception）或溢位錯誤（overflow error）不保證數字的精準度。＃維基百科 — 整數 (電腦科學)

有分型態的語言，整數的範圍

1. int（整數）：-2147483648~2147483647（-2 的 31 次方到 2 的 31 次方 — 1）
2. 在 JavaScript 中的 number 的範圍：Number.MAX_SAFE_INTEGER

我們可以實際透過程式碼來看看。

const x = Number.MAX_SAFE_INTEGER + 1;
const y = Number.MAX_SAFE_INTEGER + 2;
console.log(Number.MAX_SAFE_INTEGER);
// expected output: 9007199254740991
console.log(x);
// expected output: 9007199254740992
console.log(x === y);
// expected output: true

由上面程式碼可知道在 JavaScrtip 中只要超過 16 位數就會出錯

解法可參考：Huli — 程式解題新手入門注意事項

浮點數精准度問題

這跟電腦底層的儲存數字有關，在大部分的程式語言都會有這個問題（0.1 + 0.2 不等於 0.3），因此最好避免用到浮點數，如果真的一定要用上的話，必須將數字作轉換，以下有幾篇文章可參考：

• 抓住数据的小尾巴 — JS浮点数陷阱及解法
• 保哥 — 前端工程研究：關於 JavaScript 中 Number 型別的常見地雷與建議作法

重點整理

1. 在寫程式之前，先想好怎麼做
2. 將想法轉換成一行行的虛擬碼
3. 理解程式碼如何運作
4. 空間限制（記憶體）：JavaScript 的數字只有 number 型態，儲存空間需要 8 bitye
5. 時間限制（效能）：對初學者來說效能不是那麼重要，但往後在實作一定會需要提升效能。
6. 型態限制：JavaScript 的有限整數可以透過 Number.MAX_SAFE_INTEGER 知道，只要儲存超過 16 位數就不保證數字的精準度，而浮點數的問題存在於大部分程式語言中，因此最好盡量避免使用浮點數。

以上為先別急著寫 leetcode的學習筆記，有錯誤的地方歡迎指正，感謝。