【LeetCode】#8. String to Integer (atoi) 詳細完整解法

String to Integer (atoi)

題目敘述

實作一個將字串轉換成32-bit的有符號整數的函式myAtoi(string s)。

功能類似C/C++的atoi函式。

myAtoi(string s)內部演算法實作上有幾個規則：

• 忽略任何前置空格。
• 將'-'或'+'作為數值的正負符號表示，如果沒有符號則預設為正數。
• 持續讀取下一個字元直到字串尾或者遇到非整數，停止讀取後忽略剩下的字串。
• 將字串內的整數轉換成整數型態的數值，若字串內沒有任何整數，則回傳結果為0。
• 當數值超出整數範圍［-2^31, 2^31-1］時，將數值限制在整數型態範圍內。
• 回傳整數作為結果。

註記：

• 只有字元' '才被視為空格。
• 除了前置空格以及停止讀取後的字串，不要忽略其他字元。

其他限制條件

• 字串長度為［0, 200］。
• 字串s包含了大小寫的英文字元、數字（0-9）、空格' '、'+'、'-'、'.'。

解題思路

這一題需要處理的條件比較多，光靠題目描述沒有辦法完全涵蓋所有狀況，所以首先我們要先進行個別案例的分析。

英文字元A－Z、a－z：

英文字元是不能被忽視的字元，所以只要遇到英文字元程式就會直接結束。

Ex.

Input ："a123"
Output：0

Input ："12a3"
Output：12

Input ：" a123"
Output：0

Input ："+a123"
Output：0

Input ："-a123"
Output：0

空格' '：

題目敘述說前置空格可以被省略，但其餘字元不能被省略，所以後置空格也在其餘字元的描述內。

Ex.

Input ：" 123"
Output：123

Input ："1 23"
Output：1

正負符號'+'、'-'：

題目敘述說'+'、'-'被視為數值的正負符號被算入，所以會有以下幾種狀況：

Ex.

Input ："+123"
Output：123

Input ："-123"
Output：-123

Input ："+ 123"
Output：0

Input ："+-123"
Output：0

Input ："-+123"
Output：0

符號'.'：

符號'.'並沒有提到有什麼特殊的條件，所以將他視為與英文字元一樣的需要被排除的其餘字元。

停止讀取的條件：

停止讀取的條件為到達字串尾以及遇到非整數字元的其餘字元，透過上面的分析應該可以很清楚的釐清達成條件的案例，比較特殊的是計入'+'、'-'之後的下一個字元已經被算在轉換數值的範圍之內，要注意只要出現任何非整數字元的字元，就算是達成停止條件。

數值範圍：

數值範圍被限制在整數範圍之內，但是要注意輸入字串內的數值有可能超過整數範圍。

處理步驟：

1. 先排除所有前置空格，直到遇到不是前置空格的字元。
2. 排除前置空格後的第一格字元，若是'+'、'-'則記錄下來。
3. 若不是'+'、'-'則回傳結果為0。
4. 處理整數，遇到停止條件則回傳加上符號的整數數值。

程式碼：

class Solution {
public:
    int myAtoi(string s) {       
        long res=0;          //答案  處理字串過程中有可能超過整數數值，所以宣告為long。
        bool negative=false; //符號    
        int pos=0;           //字串位置

				//忽略前置空格
        while(s[pos]==' '){
            pos++;
        }

	      //紀錄符號
        if(s[pos]=='-'){
            negative=true;
            pos++;
        }else if(s[pos]=='+'){
            pos++;
        }
        
        //忽略空格後的字元為非整數字元
				//          or
				//紀錄符號後的字元為非整數字元
        if(s[pos]<'0' or s[pos]>'9') return 0;
        
        //處理整數字元
        for(int i=pos;i<s.length();i++){
						//停止條件，遇到非整數字元
            if(s[i]<'0' or s[i]>'9'){
                res/=10;                    //每一次加上數值後會做乘上10的進位，回傳前先除以10。
                if(negative) res=-res;      //加上符號
                if(res>INT_MAX) res=INT_MAX;//將數值限制在範圍內
                if(res<INT_MIN) res=INT_MIN;
                return res;
            }            
            res+=(s[i]-'0');           //加上數值，'0'-'0' = 0 ，'1' - '0' = 1 。
            if(res<LONG_MAX/10)res*=10;//乘上10作進位。
        }

        //停止條件，到達字串尾。
        res/=10;                    //每一次加上數值後會做乘上10的進位，回傳前先除以10。
        if(negative) res=-res;      //加上符號
        if(res>INT_MAX) res=INT_MAX;//將數值限制在範圍內
        if(res<INT_MIN) res=INT_MIN;
        
        return res;
    }
};

時間複雜度分析

最壞的狀況為從字串頭讀取到字串尾，因此為O（n）。

空間複雜度分析

沒有在函式中額外增加空間，因此為O（1）。