atoi的实现-模拟与有限自动机

  |  

摘要: 力扣8,用有限自动机识别字符串的写法

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,今天看一个非常经典的面试题,力扣8,atoi,将字符串转换为整数。由于本题在面试中过于常见,基本上大家都已经研究的非常透了,本文可以当个复习看看。

本题除了按要求模拟以外,还可以用自动机来解决。我们首先给出模拟的算法,然后构造自动机来识别字符串中的整数,最后给出的代码可以作为用自动机识别字符串的模板使用。


题目

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
2
3
4
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
0 <= s.length <= 200
s 由英文字母(大写和小写)、数字(0-9)、' '、'+'、'-' 和 '.' 组成

示例 1:
输入:s = “42”
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:”42”(当前没有读入字符,因为没有前导空格)
^
第 2 步:”42”(当前没有读入字符,因为这里不存在 ‘-‘ 或者 ‘+’)
^
第 3 步:”42”(读入 “42”)
^
解析得到整数 42 。
由于 “42” 在范围 [-231, 231 - 1] 内,最终结果为 42 。

示例 2:
输入:s = “ -42”
输出:-42
解释:
第 1 步:” -42”(读入前导空格,但忽视掉)
^
第 2 步:” -42”(读入 ‘-‘ 字符,所以结果应该是负数)
^
第 3 步:” -42”(读入 “42”)
^
解析得到整数 -42 。
由于 “-42” 在范围 [-231, 231 - 1] 内,最终结果为 -42 。

示例 3:
输入:s = “4193 with words”
输出:4193
解释:
第 1 步:”4193 with words”(当前没有读入字符,因为没有前导空格)
^
第 2 步:”4193 with words”(当前没有读入字符,因为这里不存在 ‘-‘ 或者 ‘+’)
^
第 3 步:”4193 with words”(读入 “4193”;由于下一个字符不是一个数字,所以读入停止)
^
解析得到整数 4193 。
由于 “4193” 在范围 [-231, 231 - 1] 内,最终结果为 4193 。


题解

算法1: 模拟

按照要求模拟即可,难点是分类讨论,以及边界情况,整体思路如下:

1
2
3
4
5
6
7
1. 丢弃开头的空字符
2. 第一个非空字符为有效整数字符(+-数字), 则与后续尽可能多的数字连起来
3. 除有效整数部分之外,后续的字符忽略即可,不应对结果有影响
4. 这三种情况不需要进行转换:<1>空串,<2>仅含空字符的串,<3>第一个非空字符不是有效整数字符。
5. 任何无法有效转换的情况返回 0
6. 爆INT时,根据正负返回 `INT_MIN` 或者 `INT_MAX`
7. 仅 `' '` 认为是空字符

以一个 int result 在遍历数字的阶段保存结果,初始是 0。每遍历到一个待加入到结果里的数字 iter, result 就更新为 result = result * 10 + iter

上面这一步公式是整个过程唯一可能会可能会爆 int 的地方,在执行之前,需要加一步判断。也就是这个式子 result > (INT_MAX - iter) / 10 如果成立的话,则上面的式子会爆 int,直接根据正负直接返回 INT_MAX 或是 INT_MIN

如果正常出了循环,说明此时的 result 在 [0, 2^32-1] 范围之内,不会再有爆 int 的情况,按照正负输出结果即可。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
int myAtoi(string str) {
if(str.empty())
return 0; // 空串的情况
int n = str.size();

int sign = 1;
int start = 0; // 第一个非空字符的位置
for(; start < n; ++start)
if(str[start] != ' ')
break;
if(start == n)
return 0; // 仅含空字符的情况
if(!is_digit(str[start]) && !is_sign(str[start]))
return 0; // 第一个非空字符不是有效整数字符的情况
if(is_sign(str[start]))
{
if(str[start] == '-')
sign = -1;
++start;
}

int result = 0;
// 一上来 start 就等于 n 是 +- 号之后紧跟着非数字的情况,不进循环, result 为 0 不变
while(start < n && is_digit(str[start]))
{
int iter = str[start] - '0';
if(result > (INT_MAX - iter) / 10)
{
if(sign == 1)
return INT_MAX;
else
return INT_MIN;
}
result = result * 10 + iter; // 这里有可能溢出,以上是处理
++start;
}
if(sign == 1)
return result;
else
return -result;
}

private:
bool is_digit(const char &c)
{
return c - '0' >= 0 && c - '0' <= 9;
}

bool is_sign(const char &c)
{
return (c == '+') || (c == '-');
}
};

算法2:有限自动机

有限自动机的理论可以参考编译原理的书,这里直接进行应用。

记 DFA $M = (S, \Sigma, f, S_{0}, F)$。

状态集合

首先看状态集合 $S$。

1
2
3
4
-1: 非法状态  
0: 起始的空格
1: 起始的+-
2: 整数,例如(9, -11, +191)

字母表

再看字母表 $\Sigma$。

1
2
3
4
空格
+-
0123456789
非法字符

初始状态

初始状态 $S_{0} = 0$

终结状态

终结状态 $F = {2, 3}$

状态转换图

DFA 从状态 0 开始逐字符读字符串,一边读一边更新结果。

在某字符处状态转移后,若所得状态非法,直接返回此时的结果,否则继续读下一字符,直至字符串耗尽。

当字符串耗尽,返回此时的结果。

状态转移函数 $f$ 以状态转换图表示。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
int myAtoi(string str) {
if(str.empty()) return 0;
int n = str.size();
int state = 0;
vector<bool> finals({0, 0, 1});
vector<vector<int>> transfer({
{0, 1, 2, -1},
{-1, -1, 2, -1},
{-1, -1, 2, -1},
});

int sign = 1;
long long ans = 0;
for(int i = 0; i < n; ++i)
{
state = transfer[state][_make(str[i])];
if(state < 0)
return sign * ans;
if(state == 1 && str[i] == '-')
sign = -1;
if(state == 2)
{
ans *= 10;
ans += str[i] - '0';
}
if(ans * sign <= INT_MIN)
return INT_MIN;
if(ans * sign >= INT_MAX)
return INT_MAX;
}
return sign * ans;
}

private:
int _make(const char& c)
{
switch(c)
{
case ' ': return 0;
case '+': return 1;
case '-': return 1;
default: return _number(c);
}
}

int _number(const char& ch)
{
if(ch >= '0' && ch <= '9')
return 2;
else
return 3;
}
};

Share