JavaScript
leetcode
本篇為 [ALG101] 先別急著寫 leetcode 這門課程的學習筆記。如有錯誤歡迎指正。 程式解題新手入門注意事項 - Huli
重點是在寫程式之前,先想好要怎麼做,整理自己的想法,並轉換成程式碼表達。
虛擬碼是程式碼與想法之間的橋樑,把解法用抽象的方式表示。
將剛才步驟二得到的可執行步驟翻成英文,會發現和程式碼非常相似:
更像程式碼的虛擬碼:
若以 JavaScript 撰寫成程式碼:
利用「縮排」來標明條件判斷的區塊,較容易閱讀分析。
題目: 給一個數字 n 印出 1~n 但如果碰到 3 的倍數,改印 Fizz 碰到 5 的倍數,,改印 Buzz 若同時是 3 跟 5 的倍數,印 FizzBuzz
範例:n=7
基本解法:
但此解並非最佳解法,若條件多 7 的倍數或更多,需要考慮的條件判斷也更複雜。
題目: 假設今天有一副撲克牌 一次只能看一張牌 要怎麼找到最小的牌?
解法(虛擬碼):
將上述解法翻譯成陣列:
延伸閱讀: 簡單的 FizzBuzz 藏有 深度(google 面試題) [課程學習筆記 ]先別急著寫 leetcode — 一步步打造程式腦
寫程式之前,先學會「看程式」,所謂的看程式碼 = 理解程式碼如何運作。
編譯(Compile):將高階語言所編寫的原始程式,透過編譯器(Compiler)轉成機械碼。
接著翻譯真的程式碼(JavaScript):
重點:當不知道程式碼錯在哪時,可以一行一行檢視程式碼,驗證程式碼是否符合實際想表達的。
利用 Chrome Devtool(開發者工具)Debugger,直接設置中斷點(break point),一行一行執行程式碼以找出除錯範圍。
<script>
標籤(以執行 JavaScript)底下加上 debugger
另一個 debug 的方法,也就是「log 加好加滿」,透過 log 可以得知每個階段的值。
舉例:
檢視 console 欄位結果如下,可以檢視程式碼運作是否和所想的相同,是否有進入迴圈等等。
舉例:
前後 arr
均為同一個變數,而 Chrome 會顯示該數最新儲存的值(抓取當下時間點的 log),而不是該 log 時間點的值。這個問題會出現在陣列和物件上。
利用 JSON.stringify()
將陣列或物件轉成「字串」印出,也就是深拷貝(Deep Copy)。
參考資料:
在開始寫程式碼之前,必須注意輸入範圍,因為「不同範圍可能有不同限制」,而範圍會決定解題方法。比如說排列一百萬個數字跟排序十個數字,用的方法會不相同。
在不同限制中,需注意可能會遇到下列幾種狀況:
首先,對空間有個概念:
int: 4 bytes double: bytes JS 中的 Number: 8 bytes
由此可推算出,一百萬個數字所需記憶體:
(8 * 1e6 / 1024) = 7812 KB = 7.6 MB
那麼,十億個數字所需記憶體:
(8 * 1e8 / 1024) = 781200 KB = 7600 MB = 7.4 GB
由估算過程可知,我們不可能在程式語言中,宣告一個十億個元素儲存在陣列。 勢必得用其他方法,比如把排列好的數字先放在其他檔案等等。
對初學題目來說不太重要(先求有再求好),之後會再來談 big O,用來估算時間。
把範圍講清楚的題目,才是好題目。 沒有的話就問清楚!因為範圍決定解決的方法。
目的:簡化雙層迴圈,也就是切割問題。
以「如何判斷質數」為例:
印出陣列中的質數 = 印出陣列 + 質數
Step 1. 簡化問題:不知道怎麼寫的部分,先寫成函式 isPrime
Step 2. 實作判斷質數邏輯
Step 3. 合併結果
試著把 function 加回去,程式碼會複雜很多:
Step 1. 把函式拿掉,維持主要邏輯不便
Step 2. 加上判斷質數程式碼
以「如何印出好多星星」為例:
目的:把大問題變成小問題。如果難的寫不出來,就先寫簡單的。
Step 1. 不會輸出 n 個星星,就先輸出一個就好
Step 2. 搭配函式填空法
Step 3. 利用迴圈重複加上星星
也可直接利用 repeat
函式來解題:
預期輸出:
n = 1
n = 2
n = 3
根據觀察可知規律為:
接著利用函式填空法:
加上一個輔助的函式:
再按照規律把答案填上去:
預期輸出:
首先用簡化法,產生 1*1 ~ 1*9
:
包成函式,把 1 換成 k:
其實就是再一個迴圈:
但總有一天要學會雙層迴圈,試著把上面的寫法合併:
我們可以利用 Debugger 來觀察雙層迴圈如何執行。也就是先執行外層迴圈第一圈,然後進入內層迴圈第一到九圈,執行完再回到外層迴圈第二圈,依序執行下去,用文字表示如下:
簡化法:先印出 1~100
搭配函式填空法
那麼,該如何判斷平方數呢?
開根號:Math.sqrt(n)
無條件捨去:Math.floor(n)
將 n 開根號後得到的數字,無條件捨去後再相乘,若還是等於 n 則為平方數。
另一種想法:印出平方數,直到超過 100 為止。
水仙花數(Narcissistic number)定義為:「一個 n 位數的數字,每一個數字的 n 次方加總等於自身」。
例如說 153 是三位數,而 1^3 + 5^3 + 3^3 = 153。 而數字 0~9 也都是水仙花數,因為一位數 n 的 1 次方一定會等於自己。
解題難點:
可直接判斷該數字是幾位數,但這個方法侷限於「需已知輸入範圍」,也就是必須知道有幾位數:
如何判斷幾位數:一直 / 10
取出各個數字:% 10
搭配 / 10
也可以把「數字轉成字串」,直接用字串來判斷幾位數:
例如:
判斷 [1, 3, 5, 7, 9] 是否為等差數列
解題技巧:
arr[1] - arr[0]
arr[i] - arr[i-1]
是否等於公差解題時需考慮到 Edge case(邊緣條件):
與「判斷水仙花數」題型類似。
解法一:數學解
解法二:字串偷吃步
基本上和判斷等差數列作法類似:
解一:找出比 N 小的完全平方數
解二:判斷是否為完全平方數
輸入範例:
利用二維陣列的概念,可知:
也可以直接在處理輸入後,直接輸出翻轉後的結果:
或利用回傳函式 callback 來過濾 target:
或是把字串 1!2 3
看成 1 !2!3
,迴圈內就不用再進行判斷:
有三種方式可以驗證輸出:
node index.js
,即可直接輸入數字,按 ctrl+D 輸出結果(Windows 無法執行)index.js
呼叫 functioncat input.txt | node index.js
補充:Windows 需改成 cat input.txt | env node code.js
或是 cat input.txt | command node code.js
固定輸入程式碼如下,答題時只需更改 function solve(lines):
以靈魂伴侶為例:
需注意宣告方式、縮排問題、結尾加分號等問題,修改後模板如下: