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;
    }
};