LC8. 字元串轉換整數 (atoi)

題目

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

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

讀入字元串并丢棄無用的前導空格
檢查下一個字元（假設還未到字元末尾）為正還是負号，讀取該字元（如果有）。 确定最終結果是負數還是正數。 如果兩者都不存在，則假定結果為正。
讀入下一個字元，直到到達下一個非數字字元或到達輸入的結尾。字元串的其餘部分将被忽略。
将前面步驟讀入的這些數字轉換為整數（即，"123" -> 123， "0032" -> 32）。如果沒有讀入數字，則整數為 0 。必要時更改符号（從步驟 2 開始）。
如果整數數超過 32 位有符号整數範圍 [−2^31,  2^31 − 1] ，需要截斷這個整數，使其保持在這個範圍内。具體來說，小于 −231 的整數應該被固定為 −2^31 ，大于 2^31 − 1 的整數應該被固定為 2^31 − 1 。
傳回整數作為最終結果。
           

注意：

本題中的空白字元隻包括空格字元 ' ' 。
除前導空格或數字後的其餘字元串外，請勿忽略 任何其他字元。
           

提示：

0 <= s.length <= 200
s 由英文字母（大寫和小寫）、數字（0-9）、' '、'+'、'-' 和 '.' 組成
           

示例 ：

輸入：s = "words and 987"
輸出：0
解釋：
第 1 步："words and 987"（目前沒有讀入字元，因為沒有前導空格）
         ^
第 2 步："words and 987"（目前沒有讀入字元，因為這裡不存在 '-' 或者 '+'）
         ^
第 3 步："words and 987"（由于目前字元 'w' 不是一個數字，是以讀入停止）
         ^
解析得到整數 0 ，因為沒有讀入任何數字。
由于 0 在範圍 [-231, 231 - 1] 内，最終結果為 0 。
           

思路

多else if判斷

需要考慮到每一種情況，比如s[i]為‘-’時，需要考慮s[i+1]為數字還是空格、字母等。

因每一種狀态接下來都有不同情況，通過if語句容易漏條件。

有限狀态機

對于字元串這種需要多次判斷，到達某一種狀态後還需要繼續判斷狀态，可以采用狀态機。

首先我們先分析字元串中出現的四種情況：

• 空格
• ’+‘、’-‘
• 數組字元
• 字母字元

我們可以先把在這種四種情況下會出現的狀态（即在s[i]下，s[i+1]可能存在的狀态）畫出來：

将上述四種狀态（key值）以及接下來他們要發生的狀态（value值）存儲在map中，此時可以将空格确定為第1個狀态，+、-為第2個狀态、數字為第3個狀态、字母為第4個狀态：

unordered_map<string, vector<string>> umap{
        {"start", {"start", "sign", "num", "end"}},
        {"sign", {"end", "end", "num", "end"}},
        {"num", {"end", "end", "num", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };
           

我們可以将初始狀态設為start(空格)，因為他能厘清剩下三種情況。

比如從start開始：

• 如果s的第一個字元是空格，則進入start狀态，繼續判斷下一字元
• 如果s的第一個字元是+、-，則進入sign狀态，進入數字計算，繼續判斷下一字元
• 如果s的第一個字元是空格，則進入num狀态，進入數值計算，繼續判斷下一字元
• 如果s的第一個字元是空格，則進入end狀态，結束數值計算

狀态機實質是提前将所有狀态進行記錄

代碼

多else if判斷

class Solution {
public:
    int myAtoi(string s) {
        int len = s.size();
        long long sum = 0, flag = 1, num = 0;
        for(int i=0;i<len;i++){
            if(s[i]!=' '){
                if(s[i]=='-'&&i<len-1&&s[i+1]>='0'&&s[i+1]<='9'&&num==0)
                    flag = -1;
                else if(s[i]=='+'&&i<len-1&&s[i+1]>='0'&&s[i+1]<='9'&&num==0)
                    flag = 1;
                else if(s[i]>='0'&&s[i]<='9'){
                    num++;
                    sum = sum*10+s[i]-'0';
                    if(flag*sum<-2147483648)
                        return -2147483648;
                    if(flag*sum>2147483647)
                        return 2147483647;
                }
                else
                    break;
            }
            else if(num>0)
                break;
        }
        return flag*sum;
    }
};
           

有限狀态機

class Automation{
public:
    unordered_map<string, vector<string>> umap{
        {"start", {"start", "sign", "num", "end"}},
        {"sign", {"end", "end", "num", "end"}},
        {"num", {"end", "end", "num", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };
    int get_index(char ch){
        if(ch==' ') return 0;
        if(ch=='+'||ch=='-') return 1;
        if(ch>='0'&&ch<='9') return 2;
        return 3;
    }
    string state = "start";
    int flag = 1;
    long long ans = 0;
    void get(char ch){
        state = umap[state][get_index(ch)];
        if(state=="sign"&&ch=='-')
            flag = -1;
        if(state=="num"){
            ans = ans*10+ch-'0';
            if(flag==1)
                ans = min(ans, (long long)2147483647);
            else
                ans = min(ans, (long long)2147483648);
        }
    }
};
class Solution {
public:
    int myAtoi(string s) {
        Automation a;
        for(auto ch:s)
            a.get(ch);
        return a.ans*a.flag;
    }
};