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

> 推荐阅读

>

> - CSDN主页

> - GitHub开源地址

>- Unity3D插件分享

> - 简书地址

> - 我的个人博客

> - QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

## 一、题目

### 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 位有符号整数范围 [−2³¹, 2³¹ − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^{31 的整数应该被固定为 −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小于范围[−2³¹, 2³¹ − 1]，最终结果截取为-2³¹=-2147483648

## 二、解题

### 1、思路分析

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

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

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

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

### 2、代码实现

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

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

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

```csharp

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;

​ }

​ }

​ }

​ }

}

```

执行结果：

### 3、时间复杂度

时间复杂度： O(n)

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

空间复杂度： O(1)

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

## 三、总结

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

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

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

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

| |’ '| +/-| number| other|

|–|--|–|--|–|

|start| start| signed| in_number| end|

|signed |end |end |in_number |end|

|in_number| end |end |in_number |end|

|end |end |end| end |end|