“将给定的字符串中的数字提取出来。”
题目链接: 来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/string-to-integer-atoi/
请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。
函数 myAtoi(string s) 的算法如下:
比如:
输入: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
这道题主要考察的是对于数据的处理,比如参数校验等场景的应用,在编码的时候需要认真细心的调试。
在这里需要明确转化规则,尽量根据规则编写对应的函数,对于整数的运算,需要注意溢出的问题。
通常对于可能溢出的数字,乘以10判断是否会溢出。
对于溢出的处理方式,通常将该数和 INT_MAX 除以10进行比较。
这个有个取巧的方式,就是使用正则表达式。
首先,使用字符串函数将左边的空格去掉,然后取出 符号+数字 如果可以转化为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;
}
}
}
}
}
执行结果:
时间复杂度: 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 |