LeetCode第八题：字符串转换整数 (atoi)【8/1000 python】

👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化：企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

“字符串转换整数 (atoi)”是一个经典的字符串处理问题，要求模拟 C 语言的 atoi 函数的功能。这个问题看似简单，其实不简单

问题描述

实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空白字符，直到找到第一个非空白的字符为止。

接下来的转换规则如下：

• 如果第一个非空字符是正号或负号，选择相应的符号后，尽可能将后续的数字转换为整数；
• 如果第一个非空字符是数字，则直接将其后面尽可能多的数字组合起来，形成一个整数；
• 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：如果无法进行有效的转换，返回 0。

示例： 

给定的测试用例包括：

"42" 应该返回 42
" -42"（带有前导空格的负数）应该返回 -42
"4193 with words"（数字后跟文字）应该返回 4193
"words and 987"（文字后跟数字）应该返回 0，因为在有效数字前出现非空字符
"-91283472332"（溢出32位整数范围的负数）应该返回 −2^31

解题思路

初级尝试：直接转换

一种直观的方法是尝试直接将字符串转换为整数，忽略非数字字符。

def myAtoi_v1(s: str) -> int:
    try:
        return int(s)
    except ValueError:
        return 0

问题：这个简单的方法没有考虑到题目中的所有细节，比如字符串前的空格和字符串中间的非数字字符。

由于这个版本尝试将整个字符串直接转换为整数，所以在遇到非纯数字字符串时会抛出 ValueError 异常，然后返回 0。因此，对于带有非数字字符的字符串（例如，"4193 with words" 和 "words and 987"），这个方法将不能正确处理，直接返回 0。

改进：逐字符解析

意识到直接转换的问题后，我们尝试逐字符解析字符串，按照题目的规则进行处理。

def myAtoi_v2(s: str) -> int:
    s = s.strip()
    if not s:
        return 0
    
    negative = 1
    if s[0] in ('+', '-'):
        negative = -1 if s[0] == '-' else 1
        s = s[1:]
        
    res = 0
    for char in s:
        if char.isdigit():
            res = res * 10 + int(char)
        else:
            break
    
    return max(-2**31, min(res * negative, 2**31 - 1))

问题：虽然这个方法处理了前导空格和符号，但它没有完全遵循题目的描述，比如在转换过程中的溢出检查。

这个版本能够更准确地处理前导空格、正负号和数字字符的组合，但在遇到数字后跟随的非数字字符时能正确停止解析并返回已解析的数字。对于溢出的情况，它通过在返回前进行最大/最小值的检查来处理，因此能够返回正确的溢出边界值。

最终版本：完整处理所有边界条件

在改进的基础上，我们对代码进行优化，确保能正确处理所有边界条件和溢出情况。

def myAtoi(s: str) -> int:
    s = s.strip()
    if not s:
        return 0

    negative = 1
    start = 1 if s[0] in ('+', '-') else 0
    if start and s[0] == '-':
        negative = -1

    res = 0
    for char in s[start:]:
        if char.isdigit():
            res = res * 10 + int(char)
            # 检查溢出
            if res > 2**31 - 1:
                return 2**31 - 1 if negative == 1 else -2**31
        else:
            break

    return res * negative

代码解释

• 我们先去除字符串的前导空格，然后检查第一个字符是否为正负号，据此设置 negative 变量。
• 遍历字符串的每个字符，如果是数字则加入到结果中，否则立即停止解析。
• 每次结果更新时检查是否溢出，如果溢出则根据正负号返回相应的最大或最小值。
• 最后返回解析得到的整数乘以其符号。

总结

通过逐步解决“字符串转换整数 (atoi)”问题，我们展示了在面对看似简单的问题时如何通过深入分析和反复测试来处理各种边界条件。这个过程有趣且有用，大家可以自己验证一下哦

如果本文对你有帮助，点个赞是对作者最大的鼓励!