8 字元串轉換整數(atoi)

題目

請你來實作一個 myAtoi(string s) 函數，使其能将字元串轉換成一個 32 位有符号整數（類似 C/C++ 中的 atoi 函數）。

函數 myAtoi(string s) 的算法如下：

讀入字元串并丢棄無用的前導空格

檢查下一個字元（假設還未到字元末尾）為正還是負号，讀取該字元（如果有）。 确定最終結果是負數還是正數。 如果兩者都不存在，則假定結果為正。

讀入下一個字元，直到到達下一個非數字字元或到達輸入的結尾。字元串的其餘部分将被忽略。

将前面步驟讀入的這些數字轉換為整數（即，“123” -> 123， “0032” -> 32）。如果沒有讀入數字，則整數為 0 。必要時更改符号（從步驟 2 開始）。

如果整數數超過 32 位有符号整數範圍 [−231, 231 − 1] ，需要截斷這個整數，使其保持在這個範圍内。具體來說，小于 −231 的整數應該被固定為 −231 ，大于 231 − 1 的整數應該被固定為 231 − 1 。

傳回整數作為最終結果。

示例 1：

輸入：s = “words and 987”

輸出：0

解釋：

第 1 步：“words and 987”（目前沒有讀入字元，因為沒有前導空格）

^

第 2 步：“words and 987”（目前沒有讀入字元，因為這裡不存在 ‘-’ 或者 ‘+’）

^

第 3 步：“words and 987”（由于目前字元 ‘w’ 不是一個數字，是以讀入停止）

^

解析得到整數 0 ，因為沒有讀入任何數字。

由于 0 在範圍 [-231, 231 - 1] 内，最終結果為 0 。

示例 2：

輸入：s = “-91283472332”

輸出：-2147483648

解釋：

第 1 步："-91283472332"（目前沒有讀入字元，因為沒有前導空格）

^

第 2 步："-91283472332"（讀入 ‘-’ 字元，是以結果應該是負數）

^

第 3 步："-91283472332"（讀入 “91283472332”）

^

解析得到整數 -91283472332 。

由于 -91283472332 小于範圍 [-231, 231 - 1] 的下界，最終結果被截斷為 -231 = -2147483648 。

class Solution {
public:
    int myAtoi(string s) {
        int num = 0;//儲存目前數字
        int sign = 1;//符号位
        int n = s.size();
        int i=0;//周遊指針
        //處理前導空格
        while(s[i]==' ' && i<n) i++;
        //如果i沒有越界，此時已經處理完前導空格，判斷是否有符号位
        if(s[i] == '-'){
            sign = -1;
            i++;
        }else if(s[i] == '+'){
            i++;
        }
        //繼續周遊處理數字
        for(;i<n; i++){
        	//非數字字元則結束周遊
            if(s[i]<'0'||s[i]>'9') 
                break;
            //判斷是否越界
            if(num > INT_MAX/10 || (num == INT_MAX/10 && (s[i]-'0'>INT_MAX%10))){
                return sign == 1? INT_MAX : INT_MIN;
            }
            num = num * 10 -'0' + s[i];//先減字元0防止int越界
        }
        return num*sign;
    }
};
           

• 時間複雜度O(n)
• 空間複雜度O(1)
• 思路
  • 處理前導空格
  • 判斷是否有正負号
  • 周遊字元串處理數字，遇到數字之外的則傳回目前的整數，一旦超出int的範圍則傳回int的邊界
    • INT_MAX的絕對值比INT_MIN的絕對值小，一旦數字比INT_MAX大，則一定超出int範圍。是以比較是根據INT_MAX來判斷，傳回值是根據正負号來判斷。
    • 為了避免在計算num的時候超出int範圍，要先減字元0再加上num[i]。