LeetCode刷題筆記 08 String to integer

01-29

這兩天眼角發炎，所以休息了兩天，請大家諒解。也感謝學習群里小夥伴們的關心，現在好多啦。

今天為大家帶來第8題的解題筆記。

鏈接

https://leetcode.com/problems/string-to-integer-atoi/

題目

實現atoi，將string轉成integer

釋義

這道題目重點還是考慮存在哪些可能的情況

非數字字元怎麼處理
正負號
溢出

當然，思路肯定是對string中的每一個字元進行處理，那麼怎麼把字元1轉成數字1呢?

小馬哥比較笨，想了半天沒想到

想到了可能跟ASCII表有關，但是沒能深入研究，最後偷看了答案。。。

你們就有福氣了，如果沒想到也不用去看答案了，我來告訴你們

1 - 0 = 1;n

對，和字元0相減就可以了。就是因為它們在表中是連續的

好了，關鍵問題解決了，我們再看一下幾個特殊情況要怎麼處理

非數字字元，我們可以忽略掉開頭和結尾的空字元(「 23 「)，如果數字中間有其它字元(「123x21」)，則認為後面是非法輸入
正負號，需要存下來
溢出，我們還有上一道題目的方法，用long long來處理

補充描述

我們可以根據題目的補充描述來寫一些測試用例：

「 123 」 → 123
「 -123 「 → -123
「 123x456 「 → 123
「 123 456」 → 123
「343485894858938553」 → INT_MAX
「」 → 0
「xxxyyy」 → 0

做題之前可以預習一下c++支持哪些字元操作，見《C++ Primer》第五版（中文版） P82，表3.3

萬事俱備，開始正式做題了

代碼

class Solution { npublic: n int myAtoi(string str) { nn int iFlag = 1; nn bool bStart = false; n vector<int> vecDigits; nn for( auto c : str ) n { n if( !bStart ) n { n if( isspace(c) ) n { n continue; n } nn if( (+ == c || - == c ) ) n { n iFlag = + == c ? 1 : -1; n bStart = true; n continue; n } n } nn if( isdigit(c) ) n { n bStart = true; n vecDigits.push_back( c - 0 ); n } n else n { n break; n } n } nn if( vecDigits.size() == 0 ) n { n return 0; n } nn long long result = 0; n long long iFactor = 1; nn auto i = vecDigits.size(); n while( i > 0 ) n { n --i; n result += iFactor * vecDigits[i]; n iFactor *= 10; nn if( result*iFlag > INT_MAX ) n { n return INT_MAX; n } nn if( result*iFlag < INT_MIN ) n { n return INT_MIN; n } n } nn return result*iFlag; n } n};n

邏輯有點複雜，我來解釋一下：

第一個for循環用來把合法的數字push到一個vector中
- iFlag用來保存正負號
- bStart用來保存是不是已經開始處理數字了，之所以加這個flag，是因為數字前的空格和數字後的空格處理方式不同
如果for循環之後，vector仍為空，則沒有合法數字，直接返回0
後面的while語句用來得到整數，和前一題的方式相同。這裡把溢出判斷放到了循環內部，是避免出現比long long還要長的字元串

當然，這個代碼也是做了幾次修改的，目的就是能在leetcode上通過。

然後我們再來看看能不能簡化上面的邏輯

在動手修改代碼之前，我們要思考一個問題，如何在簡化代碼的時候保證邏輯的正確性？

這是一個非常普遍的問題，在編碼的過程中我們會經常遇到。本來是想對代碼負責，做到精益求精，結果速度上去了，但是結果不對了，這就得不償失了。

要解決這個問題，可以試試「測試驅動開發」的方法，即在開始寫代碼之前先設計好測試用例，如果代碼能通過所有的測試用例，則達到了我們的功能要求。後續再進行代碼修改的時候，也要保證所有用例都能通過，如果有用例失敗了，則說明修改代碼出了問題。

正如前面我們寫的那些用例，當然這些用例肯定不夠充分，不過比什麼都不寫要強多了。要知道leetcode上這道題目有1047個測試用例！

在寫一些小程序時，我們可以使用assert來完成結果判斷。

//leetcode08.h nn#include <string nnusing std::string; nnclass Solution08 { npublic: n static int myAtoi(string str); n};n

//main nn#include "cassert" nnassert(Solution::myAtoi("123")== 123); nassert(Solution08::myAtoi("123") == 123); nassert(Solution08::myAtoi("-123") == -123); nassert(Solution08::myAtoi(" -123 ") == -123); nassert(Solution08::myAtoi(" 123 456 ") == 123);n

把上面的測試用例都補上，然後再想想還有沒有其它的場景。如果有的話，不要吝嗇使用測試用例，越多越好。

好了，已經很晚了。今天就先到這裡吧，簡化代碼的工作就留給大家了。歡迎留言或者加入學習群討論

PS:

1. 公眾號底部菜單有二維碼

2. 知乎裡面代碼高亮不太友好，這方面有要求的同學可以去公眾號