难度: 中等
标签: 字符串
请你来实现一个 myAtoi(string s)
函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi
函数)。
函数 myAtoi(string s)
的算法如下:
0
。必要时更改符号(从步骤 2 开始)。[−231, 231 − 1]
,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231
的整数应该被固定为 −231
,大于 231 − 1
的整数应该被固定为 231 − 1
。注意:
' '
。示例 1:
输入:s = "42" 输出:42 解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。 第 1 步:"42"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"42"(读入 "42") ^ 解析得到整数 42 。 由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。
示例 2:
输入:s = " -42" 输出:-42 解释: 第 1 步:" -42"(读入前导空格,但忽视掉) ^ 第 2 步:" -42"(读入 '-' 字符,所以结果应该是负数) ^ 第 3 步:" -42"(读入 "42") ^ 解析得到整数 -42 。 由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。
示例 3:
输入:s = "4193 with words" 输出:4193 解释: 第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止) ^ 解析得到整数 4193 。 由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。
提示:
0 <= s.length <= 200
s
由英文字母(大写和小写)、数字(0-9
)、' '
、'+'
、'-'
和 '.'
组成运行时间: 36 ms
内存: 14.9 MB
class Solution: def myAtoi(self, s: str) -> int: n = len(s) i = 0 while i < n: if s[i] == ' ': i += 1 else: break if i == n: return 0 if s[i] == '-': i += 1 sign = -1 elif s[i] == '+': i += 1 sign = 1 else: sign = 1 ans = 0 max_value = (1 << 31) - 1 min_value = -1 << 31 while i < n: if ord('0') <= ord(s[i]) <= ord('9'): k = ord(s[i]) - ord('0') print(ans, (min_value - k) // 10) if sign > 0 and ans > (max_value - sign * k) // 10: return max_value if sign < 0 and ans < (min_value - sign * k) // 10 + 1: return min_value ans = ans * 10 + sign * k i += 1 else: break return ans if __name__ == '__main__': s = Solution() print(s.myAtoi("-2147483649"))
该题解的思路是:首先去除字符串开头的空格,然后判断第一个非空格字符是正号还是负号,确定最终结果的符号。接着依次读取字符串中的数字字符,将其转换为整数。在转换过程中,需要判断是否超出了 32 位有符号整数的范围,如果超出则返回整数的最大值或最小值。读取到非数字字符或字符串结尾时,停止读取并返回最终的整数结果。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution: def myAtoi(self, s: str) -> int: n = len(s) i = 0 # 去除开头的空格 while i < n: if s[i] == ' ': i += 1 else: break # 如果字符串全为空格,返回 0 if i == n: return 0 # 判断符号 if s[i] == '-': i += 1 sign = -1 elif s[i] == '+': i += 1 sign = 1 else: sign = 1 ans = 0 max_value = (1 << 31) - 1 min_value = -1 << 31 # 读取数字字符并转换为整数 while i < n: if ord('0') <= ord(s[i]) <= ord('9'): k = ord(s[i]) - ord('0') # 判断是否超出整数范围 if sign > 0 and ans > (max_value - sign * k) // 10: return max_value if sign < 0 and ans < (min_value - sign * k) // 10 + 1: return min_value ans = ans * 10 + sign * k i += 1 else: break return ans
为什么在判断符号之后没有直接跳出循环,而是继续判断数字并进行转换?
在判断符号之后继续循环的目的是为了处理并转换接下来的数字字符序列。符号只告诉我们结果的正负,而真正的数值需要通过进一步读取数字字符来确定。如果在判断符号后直接跳出循环,我们将无法获得任何数字,从而使函数无法完成其将字符串转换为整数的主要功能。
在判断是否超出整数范围时,为什么使用了`(max_value - sign * k) // 10`和`(min_value - sign * k) // 10 + 1`这样的表达式?
这些表达式用于在将当前数字加到结果之前,预先检查这一操作是否会导致整数溢出。这种预检查方法是通过反向操作来实现的,即在实际执行乘法和加法之前,先按照逆运算的顺序(先除后加)检查结果是否会超过整数的界限。这样可以在不实际超出界限的情况下提前终止操作,防止溢出。
在读取数字字符并转换为整数的过程中,为什么要先判断字符是否在`'0'`到`'9'`之间?
这一步骤确保只有数字字符被转换为整数的一部分。在字符串中可能存在非数字字符,如果未进行这样的检查,则这些非数字字符会导致转换过程出错或产生非预期的输出。通过仅处理数字字符,我们可以正确地解析和转换字符串表示的数值。
题解中使用了位运算来表示最大值`max_value = (1 << 31) - 1`和最小值`min_value = -1 << 31`,为什么要这样表示?
位运算提供了一种简洁且高效的方法来表示整数的最大值和最小值。对于32位有符号整数,最大值是2^31 - 1,最小值是-2^31。使用位运算`1 << 31`直接得到2^31,然后通过适当的加减操作得到规定范围的边界值。这种表示方法在执行时非常快速,并且在代码中易于理解和维护。
在将字符转换为数字时,为什么要使用`ord(s[i]) - ord('0')`这样的方式?
这种方法是将字符型数字转换为其对应的整数值。在ASCII码表中,字符'0'到'9'是连续的,并且'0'的ASCII码值为48。通过计算`ord(s[i]) - ord('0')`,实际上是计算字符s[i]与'0'之间的距离,这恰好等于字符s[i]所代表的数值。这是一种简单且有效的转换方法。