LeetCode第八题：字符串转换整数 (atoi)
- 学习
- 2023-09-14
- 48热度
- 0评论
1.题目描述
请你来实现一个 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。 - 返回整数作为最终结果。
注意：
- 本题中的空白字符只包括空格字符
' '。 - 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
示例 1：
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。 第 1 步："42"（当前没有读入字符，因为没有前导空格） ^ 第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'） ^ 第 3 步："42"（读入 "42"） ^ 解析得到整数 42 。 由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
提示：
0 <= s.length <= 200s由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-'和'.'组成
解题思路
解法一：模拟法
- 描述：按照题目要求去完成，首先去除前导字符，然后判断正负号并且记录，遍历字符串并且整合结果，最后，处理整数溢出问题。
- 时间复杂度：O(n)。都只是进行一次遍历，n是字符串长度。
- 空间复杂度：O(1)。都是常量的额外空间。
- 参考代码：
java版：
class Solution {
public int myAtoi(String s) {
// sign是来判断正负的默认为正
// index是字符串的索引
// total是结果
int sign = 1, index = 0, total = 0;
// 如果字符串长度为0，返回0
if (s.length() == 0)
return 0;
// 去除前导空格，下面的方法选一个就行
s = s.trim();
while (index < s.length() && s.charAt(index) == ' ')
index++;
// 判断数的第一个字符如果是+就sign为1，-就置为-1，没有就默认+跳过这个判断
if (index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')) {
sign = (s.charAt(index) == '+') ? 1 : -1;
// 记得索引往后移一位，跳过正负号
index++;
}
// 遍历字符串
while (index < s.length()) {
// 获取当前字符
int digit = s.charAt(index) - '0';
// 如果不是0-9的数字，直接结束遍历
if (digit < 0 || digit > 9)
break;
// 判断溢出，溢出了就根据正负号赋值int最大和最小
if (total > Integer.MAX_VALUE / 10 || (total == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// 计算结果
total = total * 10 + digit;
index++;
}
// 最后返回要记得*符号
return total * sign;
}
}C++版：
class Solution
{
public:
int myAtoi(string s)
{
// sign是来判断正负的默认为正
// index是字符串的索引
// total是结果
int sign = 1, index = 0, total = 0;
// 如果字符串长度为0，返回0
if (s.size() == 0)
{
return 0;
}
// 去除前导空格，下面的方法选一个就行
while (index < s.size() && s[index] == ' ')
{
index++;
}
// 判断数的第一个字符如果是+就sign为1，-就置为-1，没有就默认+跳过这个判断
if (index < s.size() && (s[index] == '+' || s[index] == '-'))
{
sign = (s[index] == '+') ? 1 : -1;
// 记得索引往后移一位，跳过正负号
index++;
}
// 遍历字符串
while (index < s.size())
{
// 获取当前字符
int digit = s[index] - '0';
// 如果不是0-9的数字，直接结束遍历
if (digit < 0 || digit > 9)
{
break;
}
// 判断溢出，溢出了就根据正负号赋值int最大和最小
if (total > INT_MAX / 10 || (total == INT_MAX / 10 && digit > INT_MAX % 10))
{
return (sign == 1) ? INT_MAX : INT_MIN;
}
// 计算结果
total = total * 10 + digit;
index++;
}
// 最后返回要记得*符号
return total * sign;
}
};C版：
int myAtoi(char* s) {
int sign = 1, total = 0;
// 跳过前导空格
while (*s == ' ') {
s++;
}
// 检查正负号
if (*s == '+' || *s == '-') {
if (*s == '-') {
sign = -1;
}
s++;
}
// 遍历每个字符，直到非数字字符或字符串结束
while (*s >= '0' && *s <= '9') {
// 检查溢出
if (total > INT_MAX / 10 || (total == INT_MAX / 10 && *s - '0' > INT_MAX % 10)) {
return (sign == 1) ? INT_MAX : INT_MIN;
}
total = total * 10 + (*s - '0');
s++;
}
return total * sign;
}解法二：正则表达式法(主要是学一下正则表达式)
- 描述：利用正则表达式来找到字符串中的数字和符号，将匹配到的数字字符串转化为整数，根据获取到的正负号来判断正负，同时处理溢出错误。
- 时间复杂度：O(n)。在字符串中最多只遍历每个字符一次，n是字符串长度。
- 空间复杂度：O(n)。在我们的正则表达式中，我们只捕获了一个子字符串（匹配的数字）。这需要一个线性大小的空间，即O(n)。n是捕获子字符串的长度，对于大多数简单的匹配，如此例中的，这些数据结构通常只占用常数空间。但是，为了保守，我们可以考虑它是O(n)。在实践中，对于这个特定的正则表达式和问题，实际的空间需求更可能是O(1)，因为我们捕获的子字符串的大小相对于整个输入字符串来说是很小的，而正则表达式引擎的辅助数据结构对于这种简单的匹配也很可能是常数大小的。
- 参考代码：
java版：
class Solution {
public int myAtoi(String s) {
// 给正则表达式来编译一个模式
// 解释^\\s*([+-]?\\d+)
// 在正则表达式的开头：^ 表示匹配字符串的开头位置。例如^a会匹配a bc中的a，不会匹配bc a中的a
// 在java中\是一个转义字符，需要用到两个\\才能表示一个\,在正则表达式中\s代表任何空白字符如空格，制表符
// *在正则表达式中表示前面的字符（或字符组）可以出现0次或多次。 \\s*会匹配0个或者多个连续的空白字符
// []在正则表达式中表示满足任意一个字符，[+-]的意思是满足有+或者-
// ?在正则表达式中表示前面的字符（或字符组）是可选的，可以出现0次或1次。[+-]?就是就是可以匹配+或者-或者一个都没有
// \\d和前面一样，\d在正则表达式中代表任何数字字符即0-9
// +在正则表达式中表示前面的字符（或字符组）必须至少出现1次。\\d+就是匹配1个或者多个连续的数字字符
// ()在正则表达式中表示一个捕获组。这意味着正则表达式会“记住”匹配的那部分文本，这样你可以在后面引用或单独提取它。
// 在这种情况下，我们使用它来捕获可选的符号和后面的数字。
java.util.regex.Pattern pattern = java.util.regex.Pattern.compile("^\\s*([+-]?\\d+)");
// 将编译的模式与给定的字符串进行匹配
java.util.regex.Matcher matcher = pattern.matcher(s);
// matcher.find()是看能不能找到匹配的子序列，找到就是true 没有就是false
if (!matcher.find()) {
return 0;
}
// 上面我们用()创建了一个捕获组，group可以提取捕获组中的内容
// group(0)会返回整个匹配的文本group(1)会返回第一个捕获组的文本，以此类推
// 这里就是从匹配结果中获取第一个捕获组的内容
String matched = matcher.group(1);
int result;
// 用try catch来捕获数字异常，这里主要是捕获溢出异常
try {
// 直接将捕获的内容转化为int
result = Integer.parseInt(matched);
} catch (NumberFormatException e) {
// 溢出如果是负数
if (matched.charAt(0) == '-') {
return Integer.MIN_VALUE;
} else {
// 溢出如果是正数
return Integer.MAX_VALUE;
}
}
return result;
}
}C++版：
class Solution {
public:
int myAtoi(string s)
{
//用regex来编译和存储正则表达式。
// 解释^\\s*([+-]?\\d+)
// 在正则表达式的开头：^ 表示匹配字符串的开头位置。例如^a会匹配a bc中的a，不会匹配bc a中的a
// \是一个转义字符，需要用到两个\\才能表示一个\,在正则表达式中\s代表任何空白字符如空格，制表符
// *在正则表达式中表示前面的字符（或字符组）可以出现0次或多次。 \\s*会匹配0个或者多个连续的空白字符
// []在正则表达式中表示满足任意一个字符，[+-]的意思是满足有+或者-
// ?在正则表达式中表示前面的字符（或字符组）是可选的，可以出现0次或1次。[+-]?就是就是可以匹配+或者-或者一个都没有
// \\d和前面一样，\d在正则表达式中代表任何数字字符即0-9
// +在正则表达式中表示前面的字符（或字符组）必须至少出现1次。\\d+就是匹配1个或者多个连续的数字字符
// ()在正则表达式中表示一个捕获组。这意味着正则表达式会“记住”匹配的那部分文本，这样你可以在后面引用或单独提取它。
// 在这种情况下，我们使用它来捕获可选的符号和后面的数字。
regex pattern("^\\s*([+-]?\\d+)");
//用smatch对象来存储匹配和捕获组的结果。
smatch matches;
//regex_search用于搜索与正则表达式匹配的子字符串，三个参数分别是
//s是要搜索的字符串，smatch来存找到的结果，pattern是按照什么方式匹配
if (regex_search(s, matches, pattern))
{
try
{
//运用stoll函数的特性，如果超出long long 会抛出out_of_range异常
long long num = stoll(matches[1].str());
if (num < INT_MIN)
return INT_MIN;
if (num > INT_MAX)
return INT_MAX;
return num;
}
//当您使用&符号在异常类型前面时，您实际上是以引用的方式捕获异常对象。
//这意味着您没有创建异常对象的新副本，而是直接引用已经抛出的异常对象。
//通常，这样做更加高效，因为不涉及对象的复制。而使用const是为了保证不会修改异常对象的状态。
//如果不使用引用（即不使用& ），那么每次捕获异常时，都会创建异常对象的新副本。在许多情况下，这是不必要的，而且可能会导致性能下降。
catch (const out_of_range&)
{
//matches[1]是引用正则匹配的第一个捕获组
//str()是smatch的成员函数，用于将捕获组匹配的结果转换称字符串
//[0]是引用字符串的第一个字符
if (matches[1].str()[0] == '-')
{
return INT_MIN;
}
else
{
return INT_MAX;
}
}
}
return 0;
}
};C版：无
解法三：有限状态机
- 描述：将问题划分为管理状态和执行状态转移动作两个部分，这使得问题结构更清晰，容易扩展和调试。核心是对给定的输入，机器从一个状态转移到另一个状态，同时执行对应的动作，记得处理溢出。
- 时间复杂度：O(n)。其中 n 为字符串的长度。我们只需要依次处理所有的字符，处理每个字符需要的时间为O(1)。
- 空间复杂度：O(1)。自动机的状态只需要常数空间存储。
- 参考代码：
java版：
class Solution {
private enum State {
START, SIGNED, NUMBER, END
}
// 定义状态转移表，记录从一个状态转换到另一个状态
// 例如从开始转移到符号，就是0到1 也就是[0][1]就是SIGNED
// 从符号到数字，就是[2][3] 数字到数字就是[3][3]
private State[][] transitionTable = {
{ State.START, State.SIGNED, State.NUMBER, State.END },
{ State.END, State.END, State.NUMBER, State.END },
{ State.END, State.END, State.NUMBER, State.END },
{ State.END, State.END, State.END, State.END }
};
// 获取字符类型，一共有四种类型
// 空字符space，符号字符sign，数字字符digit，其他字符other
private int getCharType(char c) {
if (c == ' ')
return 0;
if (c == '+' || c == '-')
return 1;
if (c >= '0' && c <= '9')
return 2;
return 3;
}
public int myAtoi(String s) {
// 初始化当前状态为START，来解决前导空格问题
State currentState = State.START;
int sign = 1;
long result = 0;
// 遍历字符串的每一个字符
for (char c : s.toCharArray()) {
// 判断当前的状态通过状态转移表
// currentState.ordinal()是返回枚举的序号，getCharType(c)是字符类型
// 已经知道当前字符和将要遍历的字符，可以查表判断状态
currentState = transitionTable[currentState.ordinal()][getCharType(c)];
// 如果状态变为了符号状态，说明遍历到符号了
if (currentState == State.SIGNED) {
sign = c == '+' ? 1 : -1;
}
// 变为数字状态，就开始计算结果
else if (currentState == State.NUMBER) {
result = result * 10 + (c - '0');
// 如果是正数溢出
if (sign == 1 && result > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
// 负数溢出
if (sign == -1 && -result < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
}
// 变为结束状态直接退出循环
else if (currentState == State.END) {
break;
}
}
// 返回结果
return (int) (result * sign);
}
}C++版：
class Solution {
public:
// 定义状态，一共有四个状态
// 开始状态START，用来处理前导空格
// 符号状态SIGNED，用来判断是否遇到+或者-
// 数字状态NUMBER，表示正在读取数字
// 结束状态END，表示不在读取字符
enum State
{
START,
SIGNED,
NUMBER,
END
};
//构造函数初始化数据成员
Solution()
{
// 定义状态转移表，记录从一个状态转换到另一个状态
// 例如从开始转移到符号，就是0到1 也就是[0][1]就是SIGNED
// 从符号到数字，就是[2][3] 数字到数字就是[3][3]
transitionTable = {
{START, SIGNED, NUMBER, END},
{END, END, NUMBER, END},
{END, END, NUMBER, END},
{END, END, END, END}
};
}
int myAtoi(string s)
{
// 初始化当前状态为START，来解决前导空格问题
State currentState = START;
int sign = 1;
long long result = 0;
// 遍历字符串的每一个字符
for (char c : s)
{
// 判断当前的状态通过状态转移表
// currentState.ordinal()是返回枚举的序号，getCharType(c)是字符类型
// 已经知道当前字符和将要遍历的字符，可以查表判断状态
currentState = transitionTable[currentState][getCharType(c)];
// 如果状态变为了符号状态，说明遍历到符号了
if (currentState == SIGNED)
{
sign = c == '+' ? 1 : -1;
}
// 变为数字状态，就开始计算结果
else if (currentState == NUMBER)
{
result = result * 10 + (c - '0');
// 如果是正数溢出
if (sign == 1 && result > INT_MAX)
{
return INT_MAX;
}
// 负数溢出
if (sign == -1 && -result < INT_MIN)
{
return INT_MIN;
}
}
// 变为结束状态直接退出循环
else if (currentState == END)
{
break;
}
}
return static_cast<int>(result * sign);
}
private:
vector<vector<State>> transitionTable;
// 获取字符类型，一共有四种类型
// 空字符space，符号字符sign，数字字符digit，其他字符other
int getCharType(char c)
{
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
}
};C版：
typedef enum {
START, SIGNED, NUMBER, END
} State;
// 获取字符类型，返回值：0 = 空格, 1 = +或-, 2 = 数字, 3 = 其他
int getCharType(char c) {
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
}
int myAtoi(char* s) {
State transitionTable[4][4] = {
{START, SIGNED, NUMBER, END},
{END, END, NUMBER, END},
{END, END, NUMBER, END},
{END, END, END, END}
};
State currentState = START;
int sign = 1;
long long result = 0; // 使用 long long 避免溢出
for (int i = 0; s[i] != '\0'; i++) {
currentState = transitionTable[currentState][getCharType(s[i])];
switch (currentState) {
case SIGNED:
sign = (s[i] == '+') ? 1 : -1;
break;
case NUMBER:
result = result * 10 + (s[i] - '0');
if (sign == 1 && result > INT_MAX) return INT_MAX;
if (sign == -1 && result * sign < INT_MIN) return INT_MIN;
break;
case END:
return (int)(result * sign);
}
}
return (int)(result * sign);
}