【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)。

在〈【LeetCode】#8. String to Integer (atoi) 詳細完整解法〉中有 1 則留言

  1. 自動引用通知: 【LeetCode】 刷題地圖 - 人生自習室

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

回到頂端