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://bbs.huaweicloud.com/community/usersnew/id_1628396583336561 博客原创~