leetcode-8:字符串转换整数(有限自动机(DFA)和正则表达式)

简介: leetcode-8:字符串转换整数(有限自动机(DFA)和正则表达式)

题目

题目链接

示例 1:

输入:str = "42"
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:"42"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"42"(读入 "42")
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。

示例 2:

输入:str = "   -42"
输出:-42
解释:
第 1 步:"   -42"(读入前导空格,但忽视掉)
            ^
第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)
             ^
第 3 步:"   -42"(读入 "42")
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。

示例 3:

输入:str = "4193 with words"
输出:4193
解释:
第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)
             ^
解析得到整数 4193 。

示例 4:

输入:str = "words and 987"
输出:0
解释:
第 1 步:"words and 987"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"words and 987"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"words and 987"(由于当前字符 'w' 不是一个数字,所以读入停止)
         ^
解析得到整数 0 ,因为没有读入任何数字。
由于 0 在范围 [-231, 231 - 1] 内,最终结果为 0 。

示例 5:

输入:str = "-91283472332"
输出:-2147483648
解释:
第 1 步:"-91283472332"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"-91283472332"(读入 '-' 字符,所以结果应该是负数)
          ^
第 3 步:"-91283472332"(读入 "91283472332")
                     ^
解析得到整数 -91283472332 。
由于 -91283472332 小于范围 [-231, 231 - 1] 的下界,最终结果被截断为 -231 = -2147483648 。

解题:

可以发现这道题的边界条件非常多,如果按照这样的题目要求,需要用非常多的if语句,看起来十分杂乱。所以用自动机的方法可以让代码看起来更加有条理。

此题和剑指 Offer 67:把字符串转换成整数是一样的(c++解法)

方法一:自动机

我们也可以用下面的表格来表示这个自动机:

关于此题自动机部分解释

接下来编程部分就非常简单了:我们只需要把上面这个状态转换表抄进代码即可。

另外自动机也需要记录当前已经输入的数字,只要在 s’ 为 in_number 时,更新我们输入的数字,即可最终得到输入的数字。

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)#self.ans一直是正的,-INT_MIN也是正的
        elif self.state == 'signed':
            self.sign = 1 if c == '+' else -1 
            #因为这是state为signed情况下,只有+和-,没有符号的情况下,state就是in_number了
class Solution:
    def myAtoi(self, str: str) -> int:
        automaton = Automaton()
        for c in str:
            automaton.get(c)
        return automaton.sign * automaton.ans

方法二:正则表达式

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

使用正则表达式:

^:匹配字符串开头
[\+\-]:代表一个+字符或-字符
?:前面一个字符可有可无
\d:一个数字
+:前面一个字符的一个或多个
\D:一个非数字字符
*:前面一个字符的0个或多个

相关文章
|
1月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
34 6
|
1月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
23 0
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
23 0
|
1天前
[leetcode~数位动态规划] 2719. 统计整数数目 hard
[leetcode~数位动态规划] 2719. 统计整数数目 hard
|
存储 编译器 Linux
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
|
10天前
|
存储 算法
leetcode1237. 找出给定方程的正整数解
leetcode1237. 找出给定方程的正整数解
8 0
|
1月前
|
存储
leetcode2744. 最大字符串配对数目
leetcode2744. 最大字符串配对数目
17 0
|
1月前
leetcode2376. 统计特殊整数
leetcode2376. 统计特殊整数
15 1
|
1月前
|
Serverless
leetcode2719. 统计整数数目
leetcode2719. 统计整数数目
13 0
|
1月前
|
机器学习/深度学习 NoSQL Shell
力扣刷题-翻转字符串
力扣刷题-翻转字符串
12 1

热门文章

最新文章