2021-06-05发表2021-06-05更新刷题8 分钟读完 (大约1165个字)

leetcode-8

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$。
返回整数作为最终结果

注意：

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

官方题解

这里我们要进行模式识别，一旦涉及整数的运算，我们需要注意溢出。本题可能产生溢出的步骤在于推入，乘 10 操作和累加操作都可能造成溢出。

对于溢出的处理方式通常可以转换为 INT_MAX 的逆操作。比如判断某数乘 10 是否会溢出，那么就把该数和 INT_MAX 除10进行比较。

方法：自动机

计算机的计算（一） - 有限自动机 - 御坂研究所 (nosuchfield.com)

字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。

因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：

我们的程序在每个时刻有一个状态s，每次从序列中输入一个字符c，并根据字符c转移到下一个状态s'。

这样，我们只需要建立一个覆盖所有情况的从 s 与 c映射到 s'的表格即可解决题目中的问题。

算法中分为四个状态：开始，符号，数字，结束。

从开始状态到符号状态，通过扫描到符号可以到达

从开始状态到数字状态，通过扫描到数字到达

从开始状态到结束状态，通过扫描到其他字母到达，

从符号状态到数字状态，通过扫描到数字到达，如果是其他字符则结束

从数字状态到数字状态，通过扫描到数字到达，如果是其他字符则结束

算法

本题可以建立如下图所示的自动机：

我们也可以用下面的表格来表示这个自动机：

	‘ ‘	+/-	number	other
start	start	signed	in_number	end
signed	end	end	in_number	end
in_number	end	end	in_number	end
end	end	end	end	end

接下来编程部分就非常简单了：我们只需要把上面这个状态转换表抄进代码即可。

另外自动机也需要记录当前已经输入的数字，只要在 s'为 in_number时，更新我们输入的数字，即可最终得到输入的数字。

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

class Automaton:
    def __init__(self) -> None:
        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, s: str) -> int:
        automaton = Automaton()
        for c in s:
            automaton.get(c)
        # print(num)
        return automaton.sign * automaton.ans