8. 字符串转换整数 (atoi)：

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

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

• 读入字符串并丢弃无用的前导空格
• 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
• 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
• 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
• 如果整数数超过 32 位有符号整数范围 [−2^31^, 2^31^ − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31^ 的整数应该被固定为 −2^31^ ，大于 2^31^ − 1 的整数应该被固定为 2^31^ − 1 。
• 返回整数作为最终结果。

注意：

• 本题中的空白字符只包括空格字符 ' ' 。
• 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

样例 1：

 输入：

     s = "42"

输出：

    42

解释：

    加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
    第 1 步："42"（当前没有读入字符，因为没有前导空格）
             ^
    第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
             ^
    第 3 步："42"（读入 "42"）
               ^
    解析得到整数 42 。
    由于 "42" 在范围 [-2^31^, 2^31^ - 1] 内，最终结果为 42 。

样例 2：

输入：

    s = "   -42"

输出：

    -42

解释：

    第 1 步："   -42"（读入前导空格，但忽视掉）
                ^
    第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
                 ^
    第 3 步："   -42"（读入 "42"）
                   ^
    解析得到整数 -42 。
    由于 "-42" 在范围 [-2^31^, 2^31^ - 1] 内，最终结果为 -42 。

样例 3：

输入：

    s = "4193 with words"

输出：

    4193

解释：

    第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
             ^
    第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
             ^
    第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
                 ^
    解析得到整数 4193 。
    由于 "4193" 在范围 [-2^31^, 2^31^ - 1] 内，最终结果为 4193 。

样例 4：

输入：

    s = "words and 987"

输出：

    0

解释：

    第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
             ^
    第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
             ^
    第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
             ^
    解析得到整数 0 ，因为没有读入任何数字。
    由于 0 在范围 [-2^31^, 2^31^ - 1] 内，最终结果为 0 。

样例 5：

输入：

    s = "-91283472332"

输出：

    -2147483648

解释：

    第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
             ^
    第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
              ^
    第 3 步："-91283472332"（读入 "91283472332"）
                         ^
    解析得到整数 -91283472332 。
    由于 -91283472332 小于范围 [-2^31^, 2^31^ - 1] 的下界，最终结果被截断为 -231 = -2147483648 。

提示：

• 0 <= s.length <= 200
• s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 按字符遍历解析即可，使用状态模式可以简化逻辑。

题解：

rust：

impl Solution {
   
    pub fn my_atoi(s: String) -> i32 {
   
        let mut automaton = Automaton {
    sign: 1, ans: 0, state: State::Start };
        for c in s.chars() {
   
            automaton.get(c);
        }
        (automaton.sign * automaton.ans) as i32
    }
}

enum State {
   
    Start,
    Signed,
    InNumber,
    End,
}

impl State {
   
    fn changeState(&self, ch: char) -> State {
   
        match (self, ch) {
   
            (State::Start, ' ') => State::Start,
            (State::Start, '+') => State::Signed,
            (State::Start, '-') => State::Signed,
            (State::Start, c) if c.is_ascii_digit() => State::InNumber,
            (State::Signed, c) if c.is_ascii_digit() => State::InNumber,
            (State::InNumber, c) if c.is_ascii_digit() => State::InNumber,
            _ => State::End,
        }
    }
}

struct Automaton {
   
    sign: i64,
    ans: i64,
    state: State,
}

impl Automaton {
   
    fn get(&mut self, c: char) {
   
        self.state = self.state.changeState(c);
        match self.state {
   
            State::InNumber => {
   
                self.ans = self.ans * 10 + (c as i64 - '0' as i64);
                self.ans = if self.sign == 1 {
   
                    self.ans.min(i32::MAX as i64)
                } else {
   
                    self.ans.min(-(i32::MIN as i64))
                }
            },
            State::Signed => {
   
                self.sign = if c == '+' {
   
                     1
                } else {
   
                    -1
                }
            },
            _ =>{
   }
        }
    }
}

go：

func myAtoi(s string) int {
   
    abs, sign, i, n := 0, 1, 0, len(s)
    //丢弃无用的前导空格
    for i < n && s[i] == ' ' {
   
        i++
    }
    //标记正负号
    if i < n {
   
        if s[i] == '-' {
   
            sign = -1
            i++
        } else if s[i] == '+' {
   
            sign = 1
            i++
        }
    }
    for i < n && s[i] >= '0' && s[i] <= '9' {
   
        abs = 10*abs + int(s[i]-'0')  //字节 byte '0' == 48
        if sign*abs < math.MinInt32 {
    //整数超过 32 位有符号整数范围
            return math.MinInt32
        } else if sign*abs > math.MaxInt32 {
   
            return math.MaxInt32
        }
        i++
    }
    return sign * abs
}

c++：

class Automaton {
   
    string state = "start";
    unordered_map<string, vector<string>> table = {
   
        {
   "start", {
   "start", "signed", "in_number", "end"}},
        {
   "signed", {
   "end", "end", "in_number", "end"}},
        {
   "in_number", {
   "end", "end", "in_number", "end"}},
        {
   "end", {
   "end", "end", "end", "end"}}
    };

    int get_col(char c) {
   
        if (isspace(c)) return 0;
        if (c == '+' or c == '-') return 1;
        if (isdigit(c)) return 2;
        return 3;
    }
public:
    int sign = 1;
    long long ans = 0;

    void get(char c) {
   
        state = table[state][get_col(c)];
        if (state == "in_number") {
   
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
        }
        else if (state == "signed")
            sign = c == '+' ? 1 : -1;
    }
};

class Solution {
   
public:
    int myAtoi(string str) {
   
        Automaton automaton;
        for (char c : str)
            automaton.get(c);
        return automaton.sign * automaton.ans;
    }
};

python：

INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31

class Automaton:
    def __init__(self):
        self.state = 'start'
        self.sign = 1
        self.ans = 0
        self.table = {
   
            'start': ['start', 'signed', 'in_number', 'end'],
            'signed': ['end', 'end', 'in_number', 'end'],
            'in_number': ['end', 'end', 'in_number', 'end'],
            'end': ['end', 'end', 'end', 'end'],
        }

    def get_col(self, c):
        if c.isspace():
            return 0
        if c == '+' or c == '-':
            return 1
        if c.isdigit():
            return 2
        return 3

    def get(self, c):
        self.state = self.table[self.state][self.get_col(c)]
        if self.state == 'in_number':
            self.ans = self.ans * 10 + int(c)
            self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
        elif self.state == 'signed':
            self.sign = 1 if c == '+' else -1

class Solution:
    def myAtoi(self, str: str) -> int:
        automaton = Automaton()
        for c in str:
            automaton.get(c)
        return automaton.sign * automaton.ans

java：

class Solution {
   
    public int myAtoi(String str) {
   
        Automaton automaton = new Automaton();
        for (char c : str.toCharArray()) {
   
            automaton.get(c);
        }
        return (int) (automaton.sign * automaton.ans);
    }

    /**
     * 自动机
     */
    class Automaton {
   
        public  int   sign  = 1;
        public  long  ans   = 0;
        private STATE state = STATE.START;

        public void get(char c) {
   
            state = state.changeState(c);
            if (STATE.IN_NUMBER.equals(state)) {
   
                ans = ans * 10 + c - '0';
                ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
            } else if (STATE.SIGNED.equals(state)) {
   
                sign = c == '+' ? 1 : -1;
            }
        }
    }

    /**
     * 状态
     */
    enum STATE {
   
        START("START", "SIGNED", "IN_NUMBER", "END"),
        SIGNED("END", "END", "IN_NUMBER", "END"),
        IN_NUMBER("END", "END", "IN_NUMBER", "END"),
        END("END", "END", "END", "END"),
        ;

        private final String[] table;

        STATE(String...table) {
   
            this.table = table;
        }

        /**
         * 状态切换
         * @param c
         * @return
         */
        public STATE changeState(char c) {
   
            int col = this.getCol(c);
            return STATE.valueOf(this.table[col]);
        }

        private int getCol(char c) {
   
            if (c == ' ') {
   
                return 0;
            }
            if (c == '+' || c == '-') {
   
                return 1;
            }
            if (Character.isDigit(c)) {
   
                return 2;
            }
            return 3;
        }
    }
}

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~