leetcode 8 思路及code（带注释）

我会带着你远行 2022-10-24 13:23 71阅读 0赞

### 题目分析 ###

--------------------

> ![在这里插入图片描述][20210129234050932.png]  
> 以上是三种方法的提交结果，第一个为官方解答DFA，第二个为自己手写的if-else，最后一个为正则匹配。  
> 题目并不难，函数主要就是解决字符串转数字
> 
>  *  自己想到的就是手写，一轮循环，但是边界需要做判断
>  *  看题解有用正则表达式解决的，写法比较简答，效率也并不高
>  *  学过《形式语言与自动机》这门课，感觉也没什么用处，但是看官方题解，用到了DAF(确定的有限状态自动机)，有种学有所用的感觉

### 解题 ###

--------------------

>  *  方法一
>  *  解题思路
> 
> 1.  去掉开头的空格字符
> 2.  符号判断，正负数，需要注意特殊情况 \[+1 -> 1; ±1 -> 0\]
> 3.  循环找到数字边界
> 4.  转为整数，输出，注意题目边界要求

>  *  code  
>     python3版本，主要利用了字符串的切片操作

class Solution:
        def myAtoi(self, s: str) -> int:
            maxValue = 2 ** 31
            i = 0
            s = s.lstrip() # 去字符串最左端空格
    
            if s == '':  # 异常处理空字符串
                return 0
    
    		# 处理符号
            sign = 1
            if s[0] == '-':
                sign = -1
                i = 1
    
            if s[0] == '+':
                i = 1
    
    		# 查找字符中数字开头结尾
            start = i
            while i < len(s) and '0' <= s[i] <= '9':
                i += 1
            if start == i:
                return 0
    
            x = sign * int(s[start:i])
            if -maxValue <= x < maxValue:
                return x
            elif x < -maxValue:
                return -maxValue
            else:
                return maxValue - 1

--------------------

>  *  方法二
>  *  解题思路
> 
> 1.  正则表达式提取
> 2.  符号判断，正负数，需要注意特殊情况 \[+1 -> 1; ±1 -> 0\]
> 3.  循环找到数字边界
> 4.  转为整数，输出，注意题目边界要求

>  *  code  
>     python3版本，主要利用了字符串的切片操作

class Solution2:
        def myAtoi(self, s: str) -> int:
            ''' 1. s.lstrip() 删除字符串最左端空格字符 2. 正则表达式 ^[\+\-]?\d+， ^匹配字符串开头字符， [\+\-]？匹配0个或者一个中括号中的字符，\d表示数字字符，+表示至少一个 3. re.findall返回列表, 前面的*是解包的意思，由于取第一个数字串，故列表中只有一个元素，解包即去掉列表转为字符串，但是这里不能取 4. int(*re.findall)，找到即返回数字，否则就是0 5. 处理越界，先与最大取最小值，在与最小值取最大值 :param s: :return: '''
            return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2 ** 31 - 1), -2 ** 31)

--------------------

>  *  方法三（具体图见官方解答）
>  *  解题思路
> 
> 1.  状态转移图
> 2.  状态转移表
> 3.  程序表示状态转移表

>  *  code  
>     python3版本，主要利用了字符串的切片操作

class DFA:
        def __init__(self):
            ''' 绘制状态转移表 state为当前状态，初始为start sign为正负号标记 ans为最终答案 state_table为状态转移表 '''
            self.state = 'start'
            self.sign = 1
            self.ans = 0
            self.state_table = { 
                'start': ['start', 'signed', 'in_num', 'end'],
                'signed': ['end', 'end', 'in_num', 'end'],
                'in_num': ['end', 'end', 'in_num', 'end'],
                'end': ['end', 'end', 'end', 'end']
            }
    
        def get_col_state(self, char):
            ''' 对应每个列表下标 :param char: :return: '''
            if char.isspace():
                return 0
            elif char == '-' or char == '+':
                return 1
            elif char.isdigit():
                return 2
            else:
                return 3
    
        def get_current_state(self, char):
            ''' 获取当前状态并更新状态 获取当前值，保存符号状态 :param char: :return: '''
            self.state = self.state_table[self.state][self.get_col_state(char)]
            if self.state == 'in_num':
                self.ans = self.ans * 10 + int(char)
                self.ans = min(self.ans, MAX_SIGNED) if self.sign == 1 else min(self.ans, -MIN_SIGNED)
            if self.state == 'signed':
                self.sign = -1 if char == '-' else 1
    
    
    class Solution:
        def myAtoi(self, s: str) -> int:
            dfa = DFA()
            for c in s:
                dfa.get_current_state(c)
            return dfa.sign * dfa.ans

### 参考解题思路 ###

*  [确定的有限状态自动机（DFA）][DFA]
 *  [正则表达式提取][Link 1]

[20210129234050932.png]: /images/20221024/4cdf92dd59e84e009f6b3fa4e1b41851.png
[DFA]: https://leetcode-cn.com/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/
[Link 1]: https://leetcode-cn.com/problems/string-to-integer-atoi/solution/