Clean Code Craving

這題幾乎所有解答不是用從左往右的 Recursion 來解就是 DP 解。但我這次要用從中間開始的 Recursion 來追上 DP 的速度。 直覺的比喻 寶寶最愛玩的形狀配對盒今天要來幫助我們解題了! 為什麼我會想到用這個比喻就是之前看了一個 Reddit " Devs watching QA test the product " 一個幽默影片裡面就惡搞寶寶最愛玩的形狀配對盒子，把所有積木都丟到正方形孔去。 假設今天我們要把 " aaabcdbbc " 這串 s 測試能不能 match 一段 regular expression " a*b.*b*c "。 有 " * " 符號的我們就用一個什麼都裝的下的積木盒來代表、沒有 " * " 符號的我們用只能裝下 1 個積木的積木盒代表: 所以題目問的就是: 我們可以從左往右依序丟積木，符合積木盒上的數目要求嗎? 這樣丟就可以了: 什麼時候會失敗? 你沒丟完的時候，別想把積木藏起來: 或是有積木盒沒丟到數目要求: 但不是每一個積木盒都要丟，" x* " 類型的積木盒你不丟也無所謂: 為何不能遇到 * 就狂丟 LeetCode 第一個解答是從左往右丟積木，遇到 " x* " 的積木盒，要嘛就是丟一個要嘛就是不丟，因為後面會發生什麼事還不知道，都試試看再說。 為什麼我們遇到 " x* " 會沒辦法決定要不要丟? 舉個例子像是 s = "aaa", p = "a*a" ，如果你把 3 個 " a " 都丟到 p[0:1] 的 " a* " 那最後面的 " a " 要誰來 match? 這時候 greedy 反而會失敗，所以你只能試所有的可能性。 各個擊破 (Divide and Conquer) 有點像 Quicksort，我們先取中間的 character 找到適合的積木盒丟下去: 不過要記得每個可能性都還是要試過。要從左往右或隨機挑就隨便你了。 接著我們問說左邊剩下的 input string 可以被 match 嗎? 再問右邊可以被 match 嗎? 就這樣 ...

反轉數字就解完了 如果用字串解我們當然很直覺就想反轉字串，既然題目 "Follow up" 那邊不希望我們用字串，那我們就把數字當字串來反轉，就可以得到超乾淨的解答: class Solution { public: bool isPalindrome(int x) { if (x < 0) return false; return x == reverse(x); } int reverse(int x) { int output = 0; while (x != 0) { const int digit = x % 10; output *= 10; output += digit; x /= 10; } return output; } }; Overflow! 只是解完前幾題之後我們大概對 int 範圍都很敏感了，我們知道任意對 int 操作很容易讓他超出 [INT_MIN, INT_MAX] 的範圍，所以我們在還沒 submit 之前就大概知道上面這個解會 overflow 壞掉。 如果你看過 #7 或 #8 我的解答你可能會猜說這作者到底有什麼強迫症就是要在 int 限制下偵測 overflow，是不是又要搬出什麼 safeMultiply, safeAdd。 可是既然題目只問我能不能不要轉成 string 來解題: 當然可以啊，那我把上面 code 改一下，不轉 string 我轉 long 就不用麻煩去偵測 overflow 了: class Solution { public: bool isPalindrome(int x) { if (x < 0) return false; return (long)x == reverse(x); } long reverse(int x) { long output = 0; while (x != 0) { const int digit = x % 10; output *= 10; output += digit; x /= 10; ...

這題 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) == ' ') { ...

我知道很多人都用 string 或 long 來做這題，雖然很簡單卻沒辦法學到這題的關鍵。 LeetCode 官方解答 用了一個很 tricky 的方式偵測 overflow/underflow 恐怕也不是很通用的解。 題目的關鍵 把數字反轉根本不是重點，如果我真的要反轉數字我這樣寫就好了: class Solution { public: int reverse(int x) { int output = 0; while (x != 0) { const int digit = x % 10; output *= 10; output += digit; x /= 10; } return output; } }; 結束? 但題目希望你單純用 int 來解，而且如果結果超出 int 範圍又要 return 0，這代表我們只能用 int 來偵測甚麼時候數字會超出 int 範圍。 先了解一下 C++ Overflow/Underflow 會發生什麼事? 這就跟用什麼語言來寫非常有關係了，所以我查了一下看到這個 StackOverflow 解答 才知道原來 C++ 在執行像是 a + b 如果超出範圍的話 (overflow) 什麼狀況都有可能發生 (undefined behavior)，意味這程式已經沒救了，比 crash 還糟糕因為 a + b 有可能是任何數字。 C++ compiler 其實還有 內建的 overflow 檢查 像是  __builtin_add_overflow 來偵測什麼時候 overflow，不過我們為了學到點什麼當然不能拿來作弊。 那我們到底要怎麼偵測 a + b 會不會爆掉? 我們只要會數學的移項就好了。 移項 我們今天想偵測 a + b 是不是大於 int 最大值 (overflow)，或偵測 a + b 是不是小於 int 最小值 (underflow)，我們想知道會不會爆掉就這樣寫: return (a + b) > INT_MAX; // overflow return (a + b) < INT_MIN; // underflow 很可惜 C++ 在做左邊的 a + b 時早就爆了，這時我們就可以很...

上一篇文章 我們用了 Table 方式來嘗試解題，但程式碼有點複雜而且還比較慢。 我後來想了一下，原來我們只要畫蛇添足就可以用最快最省記憶體的方式來解這題！ 畫蛇添足法 因為題目說要擺成這個方式，我們就真的要乖乖擺成這樣嗎? 這就讓我想到之前有 9 個點要你畫 4 條直線的 思考遊戲 ，雖然我也滿討厭那個解答，不過我得說他可能貢獻了 8.7% 讓我想到下面這個方法: 如果我們把它擺成這樣方方正正的有什麼好處呢? 我們可以繼續用上一篇的 Table 方法 來解: 只是這次我們非常好判斷什麼時候他會變成 '\0' 了，主要就是因為變成方方正正的。 唯一的例外就是每個字串的第一個頭，就把他想成蛇的頭好了。 我們只要 col=0~N, row=0~M 慢慢一個一個拜訪，然後再轉成像蛇在走路的 index 去讀 s 就行了: 看到這邊我相信你應該不用什麼複雜的 index 分析就知道該怎麼解了吧? C++ 程式碼 根據上面投影片來實作，我們應該可以得到像下面這樣的程式碼: class Solution { public: std::string convert(std::string s, int numRows) { if (numRows <= 1) return s; const int numCols = s.size() / (numRows - 1) + 1; std::string output; for (int r = 0; r < numRows; r++) { for (int c = 0; c < numCols; c++) { const int snakeIndex = getSnakeIndex(r, c, numRows); const char ch = getChar(s, snakeIndex, numRows); if (ch != '\0') output += ch; } } return output; } private: char getChar(const std::string &s, const int snakeInd...

LeetCode #6 官網的 解答 第一個其實就很好了解，所以似乎這題看起來沒必要寫文章? 但我就想用一些原創、網路上找不到的方法、又簡單的把他解掉。 題目與解法 例如他把一疊標記 ABCD... 的卡片擺成這樣: 你要從左到右，從上到下的順序把卡片重新排列輸出: 當然我第一個想到的就是用 table 的方式讓他把字串擺進我的 table 中，我再來從左到右、從上到下慢慢掃就結束啦。 最後再把 "*" 的字元刪掉就好了。 因為我們變成 table 所以我們需要知道 table 的寬度才能正確計算從 2D 變成 1D 的 index，我們其實可以把它變成一個一個 group 來算: 程式碼 所以 C++ 程式碼就會長這樣: #include <algorithm> class Solution { public: std::string convert(std::string s, int numRows) { if (numRows == 1) return s; const int numColumns = calcNumColumns(s, numRows); std::string output(numRows * numColumns, '*'); int row = 0, col = 0; bool goingDown = true; for (const char c : s) { const int index = row * numColumns + col; output[index] = c; row += (goingDown ? 1 : -1); col += (goingDown ? 0 : 1); if (row == 0) goingDown = true; if (row == numRows - 1) goingDown = false; } output.erase(std::remove(output.begin(), output.end(), '*'), output.end()); return ou...

Manacher's Algorithm 被大家形容得好像是很困難的演算法。於是我在想，有沒有辦法把 Manacher's Algorithm 用好玩的方式來理解呢? 更簡單的演算法可以參考 上一篇文章 。 理解 Manacher's Algorithm 對稱半徑 回文相對於圖片就是對稱圖形的概念，我們今天的目標就是找法國、加拿大、法國國旗組在一起裡面最寬的對稱圖形: 如果我們這樣切，每個地方都可以當摺線，我們可以說對稱的地方半徑是 2: 因為往左或往右都有 2 塊。 沒有對稱的地方就是 0: 當然還有另外一種對稱是不看中間的那塊，像是文字 "aba" 我們就可以不看 "b"，像是我們可以忽略楓葉中間那塊: 對稱中的對稱 (Case 1) 這大概就是 Manacher's Algorithm 裡面最核心的概念。 假設我們已經知道有一塊半徑是 6 的對稱，如果左邊有一小塊半徑 1 的對稱，那我們可以知道右邊的對稱半徑嗎? 如果你把左半邊連數字和箭頭也當圖片的話，那右半邊不就長的一樣? 那半徑也就一樣? 沒錯，這種感覺就好像蝴蝶翅膀上面比較小的圈圈自然也會對稱在另外一邊: 被砍掉的對稱 (Case 2) 那如果有對稱超過藍色對稱的範圍怎麼辦? 像是這樣: 既然藍色對稱的範圍只到那邊，就代表他的外面一定不一樣，我們當然不能 copy 左半邊的半徑: 真可惜，不過我們會發現，我們還是可以把右半邊往中間擠到藍色對稱範圍裏面就可以對稱了: 可以更寬的對稱 (Case 3) 我們再來看最後一個 case，如果左半邊剛好碰到邊緣會發生什麼事? 這邊我把加拿大國旗中間一小塊換成藍色的: 的確這和 Case 1 看起來好像沒什麼差別，一樣的對稱半徑，But... 我們如果把右半邊的對稱稍微拉長一下，會發現，哇，右半邊有可能變更長耶，左半邊卻是沒辦法: Manacher's Algorithm 設計是當碰到這個情形就把藍色的中心點移到這個新的地方繼續跑，因為我們還沒讀到右邊邊界外，沒人知道他會變多長，這只能繼續乖乖左右慢慢拉開嘗試。 所以 Manacher's Algorithm 比 O(n^2) 演算法聰明的地方就只有重複利用上面藍色對稱的部分裡面的資訊，只要超出這個範圍，很抱歉就只好一個一個字元比...