Leetcode 第8题
文章目录
https://leetcode.com/problems/string-to-integer-atoi/submissions/
题目描述
实现一个将字符串转换成整数的atoi
。
这个函数首先会丢弃掉前面不必要的空白字符。然后从第一个非空白字符开始,输入一个可选的+
或者-
符号,符号后面跟着不限数量的数字符号,然后将这个字符串解释成一个数字。
在这个字符串的有效数字后面后面可以跟着附加的非数字字符,这些字符将会被忽略,不会影响到函数的功能。
如果字符串中第一个非空白字符不是一个有效的数字,或者在字符串中 不存在这样有效的数字序列,不需要进行转换。如果没有有效的数字字符串进行转换,返回0即可。
注意:
- 仅有空格字符
- 假设我们处于一个仅仅能够存储32位带符号整数
range = [-2^31, 2^31-1]
的环境中,如果解析出来的数字超出了可以表示的范围。INT_MAX(2^31 - 1)
或者INT_MIN(-2^31)
将会被返回。
答案示例
Example 1
|
|
Example 2
|
|
- 解释: 第一个非空白符号是
-
号,加上后面跟着的数字,可以解析出 42 来
Example 3
|
|
- 解释: 转换在遇到3之后就停止了,因为下一个字符不是数字
Example 4
|
|
- 解释: 第一个非空白字符是 w,因为既不是有效的数字也不是
+
或者-
符号,所以转换没有发生
Example 5:
|
|
- 解释: 数字
-91283472332
超出了32位数所能表示的范围,所以返回了INT_MIN(-2^31)
解题思路
看到这个题,一下子就想起了LeetCode 第65题, 可以通过状态机来解决,而且这个题目中由于忽略浮点数和科学计数法表示的数字,所以这个状态机的设计还简单一些。
首先定义输入的 token,一开始我将 Token 分成了四组,
Token | Char |
---|---|
0 | space |
1 | +/- |
3 | 0-9 |
4 | INVALID CHAR |
后来发现这种设计,对于+000023
这种情况处理起来不太友好,就将0
单独设计为一种 Token。最终设计的 Token 和 状态转换表格 如下所示:
Token | Char |
---|---|
0 | space |
1 | +/- |
2 | 0 |
3 | 1-9 |
4 | INVALID CHAR |
State | T0 | T1 | T2 | T3 | T4 |
---|---|---|---|---|---|
S0 | S0 | S1 | S4 | S2 | S3 |
S1 | S3 | S3 | S1 | S2 | S3 |
S2 | S3 | S3 | S2 | S2 | S3 |
S3 | S3 | S3 | S3 | S3 | S3 |
S4 | S3 | S3 | S4 | S2 | S3 |
- S3 是终止状态
- S1 状态可以用来确定整个数字的符号是正数还是负数
- S2 状态获得的数字都是有效的数字,需要存储起来
答案
|
|