请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
- 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
- 返回整数作为最终结果。
注意：
- 本题中的空白字符只包括空格字符 ' ' 。
- 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
第一种算法
没看答案前自己的做法。按照题目中的思路一步步写的，不断提交不通过，然后修改，然后还是提交不通过。都想放弃，看答案了，最后还是写完了。心累的懒得注释了，但是也比较简单易懂，就是分别举出正确的整数格式，不正确就退出。
def myAtoi(s):
s = s.lstrip() # 删除左侧空白字符
if len(s) == 0: return 0
if s == "+" or s == "-" or s == ".": return 0
ns, i, stop = "", 0, False
while i < len(s) - 1:
cur_c = s[i]
nex_c = s[i + 1]
if cur_c.isalpha() or cur_c == ".":
if len(ns) > 0:
stop = True
break
else:
return 0
# 符合有效整数的情况
if cur_c == "-" and nex_c.isdigit() and len(ns) == 0:
ns += (cur_c + nex_c)
elif cur_c == "+" and nex_c.isdigit() and len(ns) == 0:
ns += nex_c
elif cur_c.isdigit() and cur_c != "0":
if nex_c.isdigit():
ns += (cur_c + nex_c)
else:
ns += cur_c
stop = True
break
elif cur_c == "0" and nex_c == "0":
ns += "00" if len(ns) > 0 else ""
elif cur_c == "0" and nex_c.isdigit():
ns += (cur_c + nex_c) if len(ns) > 0 else nex_c
else:
if len(ns) > 0:
if cur_c.isdigit(): ns += cur_c
stop = True
break
else:
return 0
i += 2
if len(s)%2 == 1 and s[-1].isdigit() and not stop: ns += s[-1]
if len(ns) == 0: return 0
if int(ns) < -(2 ** 31):
return -(2 ** 31)
elif int(ns) > (2 ** 31 - 1):
return 2 ** 31 - 1
else:
return int(ns)
第二种算法
参考力扣精选答案，使用正则表达式
def myAtoi2(s):
INT_MAX = 2147483647
INT_MIN = -2147483648
str = s.lstrip() # 清除左边多余的空格
num_re = re.compile(r'^[\+\-]?\d+') # 设置正则规则
num = num_re.findall(str) # 查找匹配的内容
num = int(*num) # 由于返回的是个列表，解包并且转换成整数
return max(min(num, INT_MAX), INT_MIN) # 返回值
简单写法：
def myAtoi2(s):
return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2 ** 31 - 1), -2 ** 31)
第三种算法
参考九章算法精选答案。主要思路：先删除两边的空白字符，再判断第一位的符号是正还是负，再然后依次读后面的数字ret = ret * 10 + int(s[i])，如果不是数字就退出。
def myAtoi3(s):
s = s.strip()
if s == "":
return 0
i = 0
sign = 1
ret = 0
length = len(s)
MaxInt = (1 << 31) - 1
if s[i] == '+':
i += 1
elif s[i] == '-':
i += 1
sign = -1
for i in range(i, length):
if s[i] < '0' or s[i] > '9':
break
ret = ret * 10 + int(s[i])
ret *= sign
if ret >= MaxInt:
return MaxInt
if ret < MaxInt * -1:
return MaxInt * - 1 - 1
return ret
第四种算法
参考力扣官方答案，采用自动机算法，即DFA，全称 Deterministic Finite Automaton 即确定有穷自动机。一般用于判断比较多的情况下。
简单来说就是：先分析有哪几种状态，然后再根据各个状态再做对应的处理。
代码如下：
INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31
class Automaton:
def __init__(self):
self.state = 'start' # 默认最开始在 start 状态
self.sign = 1 # 记录整数的符号
self.ans = 0 # 整数部分
# 状态表
self.table = {
# 如果是start状态，返回0，就还是start状态；返回1，就进入signed状态
# 返回2，就进入in_number状态；返回3，就进入end状态
'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):
# 根据传入的字符和上一个state状态确定当前的state状态
self.state = self.table[self.state][self.get_col(c)]
# 如果是in_number状态，就记录整数
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)
# 如果是signed状态，就确定整数的符合
elif self.state == 'signed':
self.sign = 1 if c == '+' else -1
def myAtoi4(s):
automaton = Automaton()
# 遍历处理所有的字符
for c in str:
automaton.get(c)
return automaton.sign * automaton.ans # 返回整数
复杂度分析
- 时间复杂度：O(n)，其中 n 为字符串的长度。我们只需要依次处理所有的字符，处理每个字符需要的时间为 O(1)。
- 空间复杂度：O(1)，自动机的状态只需要常数空间存储。
参考文章：
DFA 算法
网友评论