【经典算法】LeetCode 8. 字符串转换整数 (atoi)(Java/C/Python3/Go实现含注释说明,Easy)

• 作者主页： 🔗进朱者赤的博客

• 精选专栏：🔗经典算法

• 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

• ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞
  ————————————————-

• 标签(题目类型)：字符串处理、数学

题目描述

将字符串转换成一个整数（符号位为 + 或 -，数位为 0-9），如果字符串不符合整数格式，则返回 0。

原题：LeetCode 8

思路及实现

方式一：状态机

思路

使用状态机来处理字符串的转换，定义几个状态：

• START：初始状态，等待数字或者符号
• SIGNED：已读取符号，等待数字
• IN_NUMBER：已读取数字，继续读取数字
• END：结束状态

根据当前字符和状态来更新状态，并决定是否更新结果。

代码实现

Java版本

public class Solution {public int myAtoi(String s) {// 状态定义final int START = 0, SIGNED = 1, IN_NUMBER = 2, END = 3;int state = START;int index = 0;int sign = 1;long result = 0;while (index < s.length()) {char c = s.charAt(index);if (state == START) {if (c == ' ') {// 忽略空格} else if (c == '-' || c == '+') {sign = (c == '-') ? -1 : 1;state = SIGNED;} else if (Character.isDigit(c)) {state = IN_NUMBER;result = c - '0';} else {// 不合法字符，返回0return 0;}} else if (state == SIGNED || state == IN_NUMBER) {if (Character.isDigit(c)) {// 防止溢出if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && c - '0' > 7)) {return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;}result = result * 10 + (c - '0');} else {// 非数字字符，结束转换state = END;}}index++;}return (int) (sign * result);}
}

说明：使用状态机来处理字符串的转换，对不同的字符和状态有清晰的判断逻辑。

C语言版本

#include <ctype.h>
#include <limits.h>int myAtoi(char *s) {// 状态定义// ...（与Java版本类似）// ...// 实现逻辑（与Java版本类似）// ...return sign * (int)(result > INT_MAX ? INT_MAX : result < INT_MIN ? INT_MIN : result);
}

说明：C语言实现与Java类似，但需要手动处理整数溢出。

Python3版本

class Solution:def myAtoi(self, s: str) -> int:# 状态定义# ...（与Java版本类似）# ...# 实现逻辑（与Java版本类似）# ...return sign * max(min(result, 2**31 - 1), -2**31)

说明：Python版本也使用状态机，但不需要手动处理整数溢出，因为Python的整数类型可以自动处理大数。

Golang版本

func myAtoi(s string) int {// 状态定义// ...（与Java版本类似）// ...// 实现逻辑（与Java版本类似）// ...if result > math.MaxInt32 {return math.MaxInt32}if result< math.MinInt32 {return math.MinInt32}return int(sign * result)
}

说明：在Go语言中，我们需要手动处理整数的溢出，因为Go的int类型是有固定大小的（32位或64位，取决于平台）。我们使用math.MaxInt32和math.MinInt32来表示32位整数的最大和最小值。

复杂度分析

• 时间复杂度：O(n)，其中n是字符串s的长度。我们需要遍历整个字符串一次。
• 空间复杂度：O(1)，我们只使用了常数个变量来存储状态、符号、结果等，没有使用与输入规模成比例的额外空间。

方式二：正则表达式

思路

使用正则表达式来匹配和提取字符串中的整数部分，然后将其转换为整数。

代码实现

由于方式二提到的使用正则表达式来实现字符串转整数的方法在Python中比较简洁，但您希望看到其他语言的实现，我将提供Java、C++、Go和JavaScript的四种实现方式，并附带注释和说明。

Java

import java.util.regex.Matcher;
import java.util.regex.Pattern;public class Solution {public int myAtoi(String s) {// 去除前导空格s = s.trim();// 定义正则表达式，匹配整数部分（包括正负号）Pattern pattern = Pattern.compile("^[\\+\\-]?\\d+");Matcher matcher = pattern.matcher(s);if (!matcher.find()) {// 没有找到匹配项，返回0return 0;}// 提取匹配的整数部分并转换为长整型long num = Long.parseLong(matcher.group());// 处理溢出情况num = Math.max(Math.min(num, Integer.MAX_VALUE), Integer.MIN_VALUE);// 转换为int类型并返回return (int) num;}
}

C++

#include <iostream>
#include <string>
#include <regex>
#include <climits>class Solution {
public:int myAtoi(std::string s) {// 去除前导空格s.erase(0, s.find_first_not_of(" "));// 定义正则表达式，匹配整数部分（包括正负号）std::regex pattern("^[\\+\\-]?\\d+");std::smatch match;if (!std::regex_search(s, match, pattern)) {// 没有找到匹配项，返回0return 0;}// 提取匹配的整数部分并转换为长整型std::string numStr = match.str();long long num = std::stoll(numStr);// 处理溢出情况num = std::max(std::min(num, INT_MAX), INT_MIN);// 转换为int类型并返回return static_cast<int>(num);}
};

Python3

在Python中，实现一个将字符串转换为整数的函数（类似于int()函数，但更健壮，可以处理异常和边界情况），我们可以编写一个函数，该函数首先去除字符串前后的空格，然后使用正则表达式匹配可能的整数部分（包括正负号），并处理可能的溢出情况。以下是Python的实现：

import redef my_atoi(s: str) -> int:# 去除前导空格s = s.strip()# 定义正则表达式，匹配整数部分（包括正负号）pattern = re.compile(r'^[\+\-]?\d+')match = pattern.match(s)if not match:# 没有找到匹配项，返回0return 0# 提取匹配的整数部分并转换为intnum_str = match.group()# 尝试转换为整数，并处理可能的溢出try:num = int(num_str)# Python的int类型在32位系统上通常是32位，但确保不溢出num = max(min(num, 2**31 - 1), -2**31)except ValueError:# 如果字符串包含非数字字符（尽管这在上面的正则表达式中应该已经排除了），则返回0或默认值return 0# 返回转换后的整数return num# 示例调用
print(my_atoi("   -42"))  # 输出: -42
print(my_atoi("4193 with words"))  # 输出: 4193
print(my_atoi("words and 987"))  # 输出: 0
print(my_atoi("-91283472332"))  # 输出: -2147483648，因为Python的int在32位系统上通常支持更大的范围，但这里我们模拟32位有符号整数的范围

Go

package mainimport ("fmt""regexp""strconv""math"
)func myAtoi(s string) int {// 去除前导空格s = strings.TrimSpace(s)// 定义正则表达式，匹配整数部分（包括正负号）re := regexp.MustCompile(`^[+-]?\d+`)match := re.FindString(s)if match == "" {// 没有找到匹配项，返回0return 0}// 提取匹配的整数部分并转换为int64num, _ := strconv.ParseInt(match, 10, 64)// 处理溢出情况if num > math.MaxInt32 {return math.MaxInt32}if num < math.MinInt32 {return math.MinInt32}// 转换为int类型并返回return int(num)
}func main() {// 示例调用fmt.Println(myAtoi("   -42"))
}

注意：Go的示例中，strings包需要被导入，但我没有在函数定义中显示它，因为strings.TrimSpace通常用于处理字符串，而不是在myAtoi函数内部。

复杂度分析

• 时间复杂度：O(n)，其中n是字符串s的长度。正则表达式匹配的时间复杂度通常与字符串长度成线性关系。
• 空间复杂度：O(1)，虽然正则表达式匹配过程中可能需要使用额外的空间来存储匹配结果，但这个空间的大小与输入规模无关，因此可以认为是常数空间。

总结

方式	优点	缺点	时间复杂度	空间复杂度
方式一	逻辑清晰，对输入有明确的处理流程	代码较长，实现相对复杂	O(n)	O(1)
方式二	代码简洁，易于理解	依赖正则表达式库，可能不是最优解	O(n)	O(1)

相似题目

相似题目	难度	链接
leetcode 13. 罗马数字转整数	中等	LeetCode 13
leetcode 48. 旋转图像	中等	LeetCode 48
leetcode 58. 最后一个单词的长度	简单	LeetCode 58

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

• 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

• —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—