[LeetCode][C++] 用乾淨簡單的方式解 #8 String to Integer (atoi)
這題 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:
是不是看了讓人覺得很清爽?
等等! 456 步呢?
沒錯,這題還有一個麻煩的東西我們還沒處理,就是他希望你要把數字限制在 int 能表示的範圍,不過這個借用一下 LeetCode #7 的解法就好了。
我們可以用一個 function 來 "安全地" 來算 a * 10 + x,overflow 的話就回傳 false:
因為 a 和 x 都一定是非負的數字,所以我們可以省去很多其他一般乘法判斷 overflow/underflow 的條件式。
如果途中算到一半 overflow 的話我們不只要保護 int 不超出範圍,我們還要用一個 m_overflow member variable 像記仇一樣記住這件事,最後回傳結果的時候直接傳 INT_MAX 或 INT_MIN:
一般來說如果 m_result 是 INT_MIN 的話加上負號其實是會超過 INT_MAX 會 overflow,不過我們只會 m_result * 10 + digit 而且 m_result 一開始是 0 所以 m_result 一定不是負的,自然就不用多去保護他。
所以最後的程式碼就會長這樣:
結語
Submit 完會得到又快又省記憶體的結果:
這和上一題的原因差不多,因為我們沒有用一些 string 或 long 來判斷 overflow,也沒有用太複雜的方式來解題,所以得到這結果是滿合理的。
其實上面 Steps 1-3 如果我們把那些圖合起來會得到類似 state machine 的圖,像是有人這樣解、或是這樣子。如果我們去看 JSON 官網也會看到類似的圖,其實都是在做類似的事情。我們甚至可以用比較專業的 DFA 或 NFA 去表示,不過用一大堆專業術語可不是我的目標。
GitHub
Code 和投影片我都放在 GitHub 上了,有興趣的歡迎參考。
留言
發佈留言