☆打卡算法☆LeetCode 8、字符串转换整数 算法解析

一、题目

1、算法题目

“将给定的字符串中的数字提取出来。”

题目链接： 来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/string-to-integer-atoi/

2、题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

• 读入字符串并丢弃无用的前导空格
• 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
• 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
• 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
• 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
• 返回整数作为最终结果。 注意：
• 本题中的空白字符只包括空格字符 ' ' 。
• 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

比如：

输入：s = "123" 输出：123

输入：s = " -123" 输出：-123

输入：s = "123 with words" 输出：123

输入：s = "with words 123" 输出：0 解析：首先读取字符w，因为字符w既不是空格，也不是正负符号，而且还不是一个数字，所以停止读取，返回0

输入：s = "-91283472332" 输出：-2147483648 解析：得到整数-91283472332小于范围[−231,  231 − 1]，最终结果截取为-231=-2147483648

二、解题

1、思路分析

这道题主要考察的是对于数据的处理，比如参数校验等场景的应用，在编码的时候需要认真细心的调试。

在这里需要明确转化规则，尽量根据规则编写对应的函数，对于整数的运算，需要注意溢出的问题。

通常对于可能溢出的数字，乘以10判断是否会溢出。

对于溢出的处理方式，通常将该数和 INT_MAX 除以10进行比较。

2、代码实现

这个有个取巧的方式，就是使用正则表达式。

首先，使用字符串函数将左边的空格去掉，然后取出 符号+数字 如果可以转化为int类型就直接返回。

如果不能转化为int类型，说明要不无法转化返回0，要不整数超过int的取值范围返回int最大值。

using System.Text.RegularExpressions;

public class Solution 
{
    public int MyAtoi(string s) 
    {
        s = Regex.Match(s.Trim(), @"^[+-]?\d+").ToString();
        bool t_IsParse = int.TryParse(s, out int o_Num);
        if (t_IsParse)
        {
            return o_Num;
        }
        else 
        {
            if (string.IsNullOrEmpty(s)) 
            {
                return 0;
            }
            else 
            {
                if (s[0] == '-') 
                {
                    return -2147483648;
                }
                else 
                {
                    return 2147483647;
                }
            }
        }
    }
}

执行结果：

image.png

3、时间复杂度

时间复杂度： O(n)

其中 n 为字符串的长度。我们只需要依次处理所有的字符，处理每个字符需要的时间为 O(1)。

空间复杂度： O(1)

有常数级个变量，所以空间复杂度为O(1)。

三、总结

使用正则表达式属于取巧行为，但是确实很爽，可以快速的达到目的。

但是最好还是使用算法去解决这道题，比如使用状态机去解决字符串的不同状态下的处理问题。

可以建立如下图所示的自动机：

image.png

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