力扣：字符串转换成整数（2022 |
您所在的位置：网站首页 › getchar读入空格吗 › 力扣：字符串转换成整数（2022 |
力扣：字符串转换成整数（2022
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。函数 myAtoi(string s) 的算法如下：1. 读入字符串并丢弃无用的前导空格2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还 是正数。 如果两者都不存在，则假定结果为正。3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。5. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。6. 返回整数作为最终结果。注意：本题中的空白字符只包括空格字符 ' ' 。除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/string-to-integer-atoi著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处   解法一：自写代码，时间复杂度o(n) 空格处理：字符串去除空字符，s。若字符串为空或字符长长度等于1但非数字，则返回0符号位处理：匹配符号位，去除符号位后，若非数字，返回0非数字处理：遍历字符串，遍历到非数字时，返回num转化公式：判断当前num*10+当前字符后，是否溢出，溢出返回截断数字。否则，num=num*10+当前字符class Solution(object): def myAtoi(self, s): """ :type s: str :rtype: int """ s = lstrip(s) if s=='' or (len(s)==1 and s[0].isnumeric()==False):return 0 flag=1 num=0 if s.startswith('-'): flag=0 s=s[1:] elif s.startswith('+'): s=s[1:] if s[0].isnumeric()==False:return 0 for i in s: if i.isnumeric()==False and flag==1: return num elif i.isnumeric()==False and flag==0: return 0-num elif flag==0 and num*10+int(i)>2**31: return -2**31 elif flag==1 and num*10+int(i)>2**31-1:return 2**31-1 num = num*10+int(i) if flag==1: return num else: return 0-num解法二：官方代码，时间复杂度o(n) 因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s'。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s' 的表格即可解决题目中的问题。我们可以用下面的表格来表示这个自动机：  INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31
class Automaton:
def __init__(self):
self.state = 'start'
self.sign = 1
self.ans = 0
self.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'],
}
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):
self.state = self.table[self.state][self.get_col(c)]
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)
elif self.state == 'signed':
self.sign = 1 if c == '+' else -1
class Solution:
def myAtoi(self, str: str) -> int:
automaton = Automaton()
for c in str:
automaton.get(c)
return automaton.sign * automaton.ans解法三：正则匹配 ^：匹配字符串开头[\+\-]：代表一个+字符或-字符 ?：前面一个字符可有可无 \d：一个数字 +：前面一个字符的一个或多个 \D：一个非数字字符 *：前面一个字符的0个或多个import re class Solution: def myAtoi(self, str): INT_MAX = 2147483647 INT_MIN = -2147483648 str = str.lstrip() #清除左边多余的空格 num_re = re.compile(r'^[\+\-]?\d+') #设置正则规则 num = num_re.findall(str) #查找匹配的内容 num = int(*num) #由于返回的是个列表，解包并且转换成整数 return max(min(num,INT_MAX),INT_MIN) #返回值相关函数 lstrip(str)：清除str左边多余的空格str.isnumeric()：方法检测字符串是否只由数字组成，数字可以是： Unicode 数字，全角数字（双字节），罗马数字，汉字数字str.startswith('-')：判断字符串是否以'-'为开头str.isspace()：检测字符串是否只由空白字符组成str.isdigit()：字符串是否只由数字组成re.compile()：compile 函数用于编译正则表达式，生成一个正则表达式（ Pattern ）对象，供 match() 、search() 、findall()等函数使用num_re.findall()：在字符串中找到正则表达式所匹配的所有子串，并返回一个列表，如果有多个匹配模式，则返回元组列表，如果没有找到匹配的，则返回空列表。注意： match 和 search 是匹配一次 findall 匹配所有。 正则匹配表达式学习链接：Python 正则表达式 | 菜鸟教程 |
【本文地址】
今日新闻 |
推荐新闻 |