CodeTop Top 300 热门题目5-字符串转换整数 (atoi)
力扣8题-字符串转换整数(atoi)，经典面试题
importredefmyAtoi(s:str)->int:""" 字符串转换整数 (atoi) - 力扣8题 实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。 算法步骤： 1. 丢弃无用的前导空格 2. 检查第一个字符（假设还没到末尾）是 '+' 还是 '-'，读取该符号 3. 读入数字，直到下一个非数字字符或到达输入的末尾 4. 将数字转换为整数（例如，"123" -> 123，"0032" -> 32） 5. 如果没有读入数字，则整数为 0 6. 如果整数超过 32 位有符号整数范围 [-2^31, 2^31-1]，截断为该范围 时间复杂度：O(n)，空间复杂度：O(1) """# ====== 第一步：去除前导空格 ======s=s.strip()ifnots:return0# ====== 第二步：判断符号 ======sign=1# 默认正号index=0ifs[0]=='-':sign=-1index=1elifs[0]=='+':index=1# 如果第一个字符是数字，index 保持为 0# ====== 第三步：读取数字 ======result=0INT_MAX=2**31-1# 2147483647INT_MIN=-2**31# -2147483648whileindex<len(s)ands[index].isdigit():# 获取当前数字字符的值digit=int(s[index])# ====== 第四步：检查溢出（关键！）=======# 在相加之前判断是否会溢出ifresult>(INT_MAX-digit)//10:# 如果是正数，返回 INT_MAX# 如果是负数，返回 INT_MINreturnINT_MAXifsign==1elseINT_MIN# 当前位累加result=result*10+digit index+=1# 应用符号returnsign*result# ====== 方法二：使用正则表达式（简洁但效率稍低）======defmyAtoi_regex(s:str)->int:""" 使用正则表达式的解法 正则表达式解释： ^[\+\-]? # 可选的正负号 \d+ # 一个或多个数字 """pattern=r'^[\+\-]?\d+'match=re.match(pattern,s.strip())ifnotmatch:return0# 提取匹配到的数字字符串num_str=match.group()# 转换为整数并处理溢出INT_MAX=2**31-1INT_MIN=-2**31num=int(num_str)# 处理溢出ifnum>INT_MAX:returnINT_MAXifnum<INT_MIN:returnINT_MINreturnnum# ====== 方法三：自动机（状态机）解法（进阶）======defmyAtoi_dfa(s:str)->int:""" 使用确定性有限自动机(DFA)的解法 状态定义： - start: 初始状态 - signed: 已读取符号 - in_number: 正在读取数字 - end: 结束状态 状态转移： start -> start (空格) start -> signed (+/-) start -> in_number (数字) start -> end (其他) ...以此类推 """# 定义状态转移表# 状态: [空格, 符号(+/-), 数字, 其他]state_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']}# 当前状态state='start'sign=1result=0INT_MAX=2**31-1INT_MIN=-2**31forcharins:# 判断字符类型ifchar==' ':char_type=0# 空格elifcharin'+-':char_type=1# 符号elifchar.isdigit():char_type=2# 数字else:char_type=3# 其他# 状态转移state=state_table[state][char_type]# 根据状态执行操作ifstate=='signed':sign=1ifchar=='+'else-1elifstate=='in_number':digit=int(char)# 检查溢出ifresult>(INT_MAX-digit)//10:returnINT_MAXifsign==1elseINT_MIN result=result*10+digitreturnsign*result# ====== 测试用例 ======if__name__=="__main__":# 测试用例1：正常情况print(myAtoi("42"))# 输出: 42# 测试用例2：带前导空格和负号print(myAtoi(" -42"))# 输出: -42# 测试用例3：前导空格和正号print(myAtoi("4193 with words"))# 输出: 4193# 测试用例4：非数字开头print(myAtoi("words and 987"))# 输出: 0# 测试用例5：正号后无数字print(myAtoi("+-12"))# 输出: 0# 测试用例6：正溢出print(myAtoi("91283472332"))# 输出: 2147483647 (INT_MAX)# 测试用例7：负溢出print(myAtoi("-91283472332"))# 输出: -2147483648 (INT_MIN)# 测试用例8：边界值测试print(myAtoi("2147483647"))# 输出: 2147483647 (刚好INT_MAX)print(myAtoi("-2147483648"))# 输出: -2147483648 (刚好INT_MIN)# 测试用例9：前导零print(myAtoi(" -0000000000000012"))# 输出: -12# 测试用例10：测试正则版本print(myAtoi_regex("4193 with words"))# 输出: 4193# 测试用例11：测试DFA版本print(myAtoi_dfa(" -42"))# 输出: -42详细解释
题目难点
这题看似简单，但有很多边界条件需要处理：
- 前导空格：
" 42"→42 - 正负号：
"+42"、"-42" - 非数字字符终止：
"4193 with words"→4193 - 前导零：
"00042"→42 - 无效输入：
"words 42"→0 - 正溢出：
"91283472332"→2147483647 - 负溢出：
"-91283472332"→-2147483648
方法一：常规解法（推荐）
核心步骤：
- 去除空格：
strip()去除前导和后导空格 - 判断符号：检查第一个字符是否为
+或- - 读取数字：遍历字符，遇到非数字停止
- 处理溢出：关键！在累加之前判断是否会溢出
溢出判断的关键：
ifresult>(INT_MAX-digit)//10:returnINT_MAXifsign==1elseINT_MIN为什么要这样判断？
- 下一步是
result * 10 + digit - 如果
result * 10 + digit > INT_MAX就会溢出 - 移项：
result > (INT_MAX - digit) // 10
注意：判断要在乘法之前，不能等溢出后再判断！
方法二：正则表达式
优点：代码简洁
缺点：效率稍低，但面试中也常用
正则^[\+\-]?\d+解释：
^字符串开始[\+\-]?可选的正负号\d+一个或多个数字
方法三：状态机（DFA）
适用场景：
- 对状态变化有严格要求
- 需要清晰的状态转移逻辑
- 面试官要求"设计一个状态机"
状态转移表：
当前状态 \ 输入字符 空格 符号 数字 其他 start start signed in_number end signed end end in_number end in_number end end in_number end end end end end end复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 常规解法 | O(n) | O(1) |
| 正则解法 | O(n) | O(n) |
| DFA解法 | O(n) | O(1) |
n 是字符串长度
易错点总结
- 溢出判断时机：要在累加前判断，不是累加后
- 符号处理：符号只有第一个字符才有效，后续的
+-会终止解析 - 前导零：直接转整数即可，
int()会自动处理 - 空字符串：
strip()后要检查是否为空 - 负溢出边界：
-2147483648是有效的，不要错误处理