Python 版 LeetCode 刷题笔记 #8 字符串转换整数 (atoi)

今天趁着有兴致多刷一道，中等难度的题，这种题考虑的情况比较多，写完之后只能靠提交了看测试结果，针对返回的特殊测试用例来完善代码。大概提交了四次，我的代码通过了。题目挺长，走起～

题目

中文题目

第 8 题 字符串转换整数 (atoi)：

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

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

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示： 本题中的空白字符只包括空格字符 ' ' 。 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。

示例：

输入: "42"
输出: 42

输入: "   -42"
输出: -42

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−2^31) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

英文题目

Question 8 String to Integer (atoi):

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character ' ' is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. If the numerical value is out of the range of representable values, INT_MAX (2^31 − 1) or INT_MIN (−2^31) is returned.

Example:

Input: "42"
Output: 42

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.Then take as many numerical digits as possible, which gets 42.

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer. Thefore INT_MIN (−2^31) is returned.

题目描述的内容算是清晰，就是对出现的字符情况要做些说明，结合这具体输入输出的例子还是便于理解的。

思路

可能会想到正则匹配吧，但这种练习题就先不考虑了。既然把字符串转化为整数，那么对字符遍历在所难免。那初步想法就是在遍历时判断字符类型：如果是 “+” 或 “-” 出现，那么下一位必须是数字，否则返回 0；如果是数字出现，那么下一位如果还是数字就继续遍历、如果非数字那么结束遍历；如果是空格，继续下一位；如果不是上述，可以提前返回 0 了。最终如果完成了整个遍历并取到了结果数字，再检测是否超出 32 位的限制，返回对应值，任务完成。

代码

class Solution:
    def myAtoi(self, str: str) -> int:
        # 用于判断下一位是否必须为数字的标志
        next_digit = False
        # 用于提取数字结果的字符串
        result = ""
        # 这里的 str 是输入的变量名，与方法还重名了
        for c in str:
            # 根据标志判断下一位是否必须为数字
            if next_digit:
                # 如果是数字，添加到结果中
                if c.isdigit():
                    result+=c
                # 如果下一位必须为数字、但不是数字，结束后续遍历
                else:
                    break
            # 若下一位不受限制、比如刚开始第一位、或者前一位为空格
            else:
                # 如果空格，进行下一位的判断
                if c==" ":
                    continue
                # 如果为 + ，下一位必须为数字
                elif c=="+":
                    next_digit = True
                # 如果为 - ，下一位必须为数字，且把符号加到结果中
                elif c=="-":
                    next_digit = True
                    result += c
                # 如果为数字，加到结果中，且下一位必须为数字
                elif c.isdigit():
                    result +=c
                    next_digit=True
                # 非以上字符
                else:
                    # 如果之前检测到了数字，提前结束遍历
                    if result and result[-1].isdigit():
                        break
                    # 其它情况直接返回 0
                    else:
                        return 0
        # 结束遍历到这里，通过 try 来避免转化整数报错、报错说明无法转化为整数，直接返回 0
        try:
            # 如果正常转化为整数，
            num = int(result)

            # 判断是否超过 32 位上下边界的限制
            right = 2**31-1
            left = -1-right
            # 超过限制就返回边界值，否则返回该值
            if num>right:
                return right
            elif num<left:
                return left
            else:
                return num
        except:
            return 0

提交答案

这次运行结果上，用时表现不错，内存消耗挺惨：

中文区结果：

执行用时 : 44 ms, 在所有 Python3 提交中击败了 65.63% 的用户 内存消耗 :13.8 MB, 在所有 Python3 提交中击败了 7.14% 的用户

英文版结果：

Runtime: 20 ms, faster than 99.42% of Python3 online submissions for String to Integer (atoi). Memory Usage: 14 MB, less than 5.95% of Python3 online submissions for String to Integer (atoi).

英文版结果时间上亮瞎狗眼，可见设计还挺合理的，哈哈。

优化

代码中一堆 if 判断，看了脑壳疼，得要点耐心。翻看别人的解法，传说中的一行代码又出现了，来观摩吧：

class Solution:
    def myAtoi(self, str: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', str.lstrip())), 2**31 - 1), -2**31)

#链接：https://leetcode-cn.com/problems/string-to-integer-atoi/solution/python-1xing-zheng-ze-biao-da-shi-by-knifezhu/

表现结果：

Runtime: 28 ms, faster than 88.60% of Python3 online submissions for String to Integer (atoi). Memory Usage: 14 MB, less than 5.95% of Python3 online submissions for String to Integer (atoi).

我们现在要做的就是搞懂这一行代码的实现过程，看其中有什么可以学习的点。看到 re 这是直接用了正则表达式了。str.lstrip() 这个在很多字符串的入门教程里会提到，去除左侧的空白符。这个 max() 和 min() 的嵌套就有点骚了，就这么融合在一起了。唯一看不太明白的是这个 re 前面的星号 * 。

不着急，分解下代码来看：

import re
def myAtoi(s: str) -> int:
    x = re.findall('^[\+\-]?\d+', s.lstrip())
    print(x)
    return max(min(int(*x), 2**31 - 1), -2**31)

将 int(一堆内容) 中的内容提取出来，最初我是连带着一起提出来的，结果报错，就把星号留在 int(x) 内了，通过打印、或者分析可以看出 x 是一个包含了正则匹配完结果的列表，那么这里的星号配合列表就清晰了：列表前面加星号作用是将列表解开、元素作为独立的参数传入后续函数。

比如这里我们正则完得到 ['123'] 列表，int(*['123']) 就相当于 int('123') 得到 123 。至于代码中的 re 正则表达式使用呢，用得多就熟练了，我反正是现用现查、不查看得懂，就先不理了。

再回头看下那个 max(min(value, 最大边界), 最小边界) 的嵌套应用，一行代码实现边界限制，学到了学到了。

结论

第八题，中等难度，有些耐心还是能应付来的。这次代码中自己写时用到 str.sdigit() 函数来判断字符是否只是数字。也用到了 try: except 来解决报错，试了下可能也就传入空字符串时会触发这个报错情况。

在观摩一行代码的答案时，也是有 str.lstrip() 这个用法可以拿来借鉴，直接去除左侧空白字符，同时 * 对列表的解包也有了一定认识，以及最后 max() 和 min() 的嵌套之后也可以尝试了。收获多多，满足。

今天时间充沛，连刷两道题，进度赶到八天八道题了，开心～