Clean Code Craving

又是一個資料結構練習? 但仔細一看他希望我們做 one pass 就可以輸出答案。 我 OK，你先走 n 步 如果我們用左右兩個指標，讓右邊的指標先走 n 步，會發生什麼事? 我們就先模擬看看，當右邊的人一踩到 nullptr ，左邊的指標在哪? 假設 n=2 我們看到左邊的指標正好指著要刪除的 node，好像就做完了。 問題是，現在要怎麼刪除左邊的人? 單向的 linked list 一旦往後走就不能回頭了，我們想把 2 接到 4 現在就卡死動彈不得了。 我 OK，你先走 n + 1 步 既然我們想要把左右兩邊的指標再距離寬一點，那我們就會很直覺的想把 n + 1 再模擬看看: 但如果 n 剛好等於 linked list 長度，右邊先跑 n + 1 步的話左邊的人不就會超出範圍? 所以我們就用一個常見的技巧，創一個虛擬的 node，LeetCode 上叫做 dummy ，不過我覺得叫 root 比較好，比較有起始點的感覺。 當右邊指標撞到 nullptr 左邊指標的下一個人剛好就是要刪除的對象，這時候就不會有問題。 Boundary Cases 養成好習慣我們還是要稍微想一下比較容易出問題的邊界條件: 如果 n=1 會不會有問題? 不會 如果 n=size 會不會有問題? left 會在 root 的位置，刪除下一個人也不會有問題 好讀的 C++ 程式碼 我們想要讓維護的人一看就知道程式碼在做什麼，所以我的習慣就是用小小的 function 加上很好懂得名稱告訴別人我 function 在做什麼，而且一次只做一件事。 這樣  removeNthFromEnd 就會看起來很清爽: class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { ListNode root(0, head); ListNode *left = &root; ListNode *right = &root; right = moveNSteps(right, n + 1); while (right != nullptr) { left = moveNSteps(left, 1); right...

這一題很簡單，感覺就是在練習資料結構居多，但是很容易就會寫得很亂... Function 太多行了 我自己一開始練習就寫出像下面這樣子的 C++ code: class Solution { public: ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { ListNode *curNode = new ListNode(); ListNode *head = curNode; int carry = 0; while (true) { const int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry; carry = sum / 10; curNode->val = sum % 10; l1 = l1 ? l1->next : l1; l2 = l2 ? l2->next : l2; if (!l1 && !l2 && !carry) { break; } curNode->next = new ListNode(); curNode = curNode->next; } delete curNode->next; curNode->next = nullptr; return head; } }; 如果我不跟你說題目是什麼，看到的話會覺得這蝦米? 如果你現在上網搜尋其他解答，會發現大家解答好像都長得差不多，反正就是一個 while 裡面做一大坨事。 仔細分析一下我們會發現為什麼通常我們都會寫出很複雜的 code: 我們同時要 traverse 兩個 linked list 我們同時要輸出到一個越長越長的 linked list 我們同時又要算加法，把 carry 帶到下一位 我們把三件事混在一起，當然程式碼會很複雜。 Clean Code 如果我們把上面說的那三件事切開來處理，變成多個 functions，一個 function 專心做一件事，會不會好看一點呢...

這題稍微分析一下數學就可以讓程式快 2 倍，但大家好像都沒這樣做。 "簡單的"數學分析 題目要我們找三個數字加起來等於 0: num1 + num2 + num3 = 0 如果我們每個數字分成正負號的話，什麼情況下這個式子一定無法成立? 我們要加快程式就是要省去一些運算，所以如果有一開始就知道不用算的東西那我們就最開心了。 我們會發現 3 個數字都正號或 3 個數字都負號你連算都不用算，因為全部加起來不是大於 0 就是小於 0: num1(-) + num2(-) + num3(-) < 0 -> No solution num1(+) + num2(+) + num3(+) > 0 -> No solution 那麼剩下的情況我們就一定有正有負: num1(-) + num2(-) + num3(+) = 0 num1(+) + num2(+) + num3(-) = 0 知道了這件事我們就可以不用傻傻的跑去計算 3 個正數或是 3 個負數的情況了。 想法: 找 num3 數學為什麼有用在這邊就又得了一分，你看到上面都只剩兩種可能性了，那演算法已經呼之欲出了: 我們用任意 2 個負數來找剩下 1 個正數存不存在 我們用任意 2 個正數來找剩下 1 個負數存不存在 這時候我們在想演算法的時候大概會這樣想: 任意 2 個數? 那我就用 2 個 for loop 來暴力組合兩個數字 來找一個數字在不在? 我可以用 hash table 用 O(1) 時間找到他 可是 for loop 暴力解通常是建立在數字已經從小到大排好，而且沒有重複的數字的前提下，所以我們大概是躲不掉排序 + 移除重複的數字的這兩個步驟。 演算法: 找 num3 在移除重複的數字前我們先想要知道每個數字有幾個，這個步驟很重要我們後面就知道為什麼: 然後我們就 sort + 移除重複的數字: 接著我們就試著把所有可能的 2 個負數 num1 + num2 加起來，再來找正的 num3 在不在: (如果影片無法播放可以來看 PowerPoint 投影片 ) 再來我們試著把所有可能的 2 個正數 num1 + num2 加起來，再來找負的 num3 在不在: 實作: 用 map Hash table 要用什麼資料結構? 第一個想到的當...

阿拉伯數字 -> 羅馬數字 回顧一下 LeetCode #12 ，我們觀察羅馬數字一定是從大排到小: 如果要轉回數字，我們按照顏色的區塊也是從大到小轉回來就好了。 要小心的陷阱 這題目其實一點都不 Easy，如果你從左到右讀字串，最容易遇到的問題就是: 如果你讀到一個字元 "I" 就很開心的以為這是 1，但其實他只是 "IV" = 4 的一部分怎麼辦? 所以大部分解答都花了很多力氣去處理這類的問題，看了 code 就會覺得很頭痛。 轉換的順序 Step Symbol Value 1 M 1000 2 CM 900 3 D 500 4 CD 400 5 C 100 6 XC 90 7 L 50 8 XL 40 9 X 10 10 IX 9 11 V 5 12 IV 4 13 I 1 如果我們按照上面這樣 Step 1~13 看 string 前面長的一樣就加上數字，不一樣就去下一個 step，永不回頭，會有什麼問題嗎? 前面我們說可能會搞混的像是 IV=4 和 I=1，可是 Step 12 先判斷最不合群的 "IV" = 4，失敗了 Step 13 再去判斷是不是 "I" = 1 或 "II" = 2 或 "III" = 3，就不可能會搞混 1~4 的數字。 其他更大的數字也是如此，你可以抓兩個容易搞混的羅馬數字試試看。 C++ Code 我們就按照 Step 1~13 慢慢判斷，程式碼就會長得像這樣: struct RomanAndValue { std::string romanStr; int value = 0; }; class Solution { public: int romanToInt(std::string s) { static cons...

這題 Acceptance rate 是 LeetCode 前幾名最低的，只有 16% 左右，看似複雜但其實可以變成很簡單，只要我們把問題切成小塊來處理就好了。 何謂 Read In? 有沒有發現題目描述提到很多次 "Read in"? 其實每次 Read in 就是把一個 character 給吃掉的意思: 在 Parse 字串的時候有時候你會想要吃掉 character，有時候卻又不想吃掉。像是如果突然讀到一個數字字元 "4"，但這時候還在決定正負號怎麼辦? 那當然就是不要吃掉這個字元，留給負責處理數字的步驟去處理。 Easy As 123 既然題目描述都跟你說 1、2、3 步要做什麼了，我們可以就寫相對應的 functions 一個專心處理一件事就好。 第一步我們先看看要不要狂吃空白字元，認不得的東西就算了丟給第二步: 這邊如果你看到我標示的 "Read" 亮框就表示每走過一次箭頭就應該要把一個字元吃掉。 第二步我們來看看正負號，決定最後到底是正是負: 第三步我們就狂吃數字字元，直到沒辦法再吃為止: 如果看了這三張投影片，我們不管用什麼程式語言應該都可以寫出 code 來了。 如果我用 C++ 寫就會寫出像這樣的 code: class Solution { public: int myAtoi(std::string s) { int index = 0; while (runStep1(s, index /*may change*/)) ; while (runStep2(s, index /*may change*/)) ; while (runStep3(s, index /*may change*/)) ; if (!m_positive) m_result *= -1; return m_result; } bool runStep1(const std::string &s, int &index) { if (index >= s.size()) return false; if (s.at(index) == ' ') { ...