[面试题] Java实现字符串转整数(atoi)：详解边界处理与两种解题思路

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

该函数的处理逻辑非常明确：

1. 忽略前导空格：读入字符串并丢弃无用的前导空格。
2. 检查符号：检查下一个字符（假设还未到末尾）是正号 + 还是负号 -，并读取该字符（如果有）。根据符号确定最终结果的正负。如果两者都不存在，则假定结果为正。
3. 读取数字：继续读入字符，直到到达下一个非数字字符或输入结尾。字符串的其余部分将被忽略。
4. 转换整数：将前面步骤读入的数字字符转换为整数（例如，"123" -> 123，"0032" -> 32）。
5. 处理无数字情况：如果没有读入任何数字，则整数为 0。最后根据第二步记录的符号应用符号。
6. 处理溢出：如果转换出的整数数值超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，则需要进行截断。具体来说，小于 −2^31 的整数应被固定为 −2^31 ，大于 2^31 − 1 的整数应被固定为 2^31 − 1。
7. 返回结果：返回最终的整数。

注意：

• 本题中的空白字符只包括空格字符 ' '。
• 除前导空格或数字之后的字符串外，不应忽略任何其他字符。

示例解析

• 示例 1：
  输入：s = "42"
  输出：42
  解释：没有前导空格，无符号（默认为正），读取数字”42”，未溢出。

• 示例 2：
  输入：s = " -42"
  输出：-42
  解释：忽略前导空格，读取符号’-’，读取数字”42”，应用符号。

• 示例 3：
  输入：s = "4193 with words"
  输出：4193
  解释：读取数字”4193”后遇到空格（非数字字符），停止读取。

• 示例 4：
  输入：s = "words and 987"
  输出：0
  解释：第一个非空字符是’w’，既非符号也非数字，直接返回 0。

• 示例 5：
  输入：s = "-91283472332"
  输出：-2147483648
  解释：转换出的数字 -91283472332 小于 −2^31，因此被截断为 −2^31。

提示：

• 0 <= s.length <= 200
• s 由英文字母（大小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成。

思路与解答

方法一：基础遍历法（手动解析）

这道题虽然题目描述较长，但核心逻辑清晰：按照规则逐步解析字符串。关键在于处理以下边界情况：

1. 跳过所有前导空格。
2. 第一个非空字符必须是数字或正负号。
3. 记录符号，无符号默认为正。
4. 连续读取数字字符，遇到非数字字符立即停止。
5. 在累加数字的过程中，必须实时判断是否会导致溢出。

核心转换逻辑：
将数字字符累加为整数的核心代码为：

sum = sum * 10 + (str.charAt(i) - '0');

这是一个处理数字字符串的经典算法技巧。

溢出判断：
溢出检查需要在累加 (sum * 10 + digit) 之前进行。我们以 Java 中 Integer.MAX_VALUE = 2147483647 和 Integer.MIN_VALUE = -2147483648 为例：

• 正数溢出：如果当前 sum > Integer.MAX_VALUE / 10，那么 sum * 10 必定溢出；或者 sum == Integer.MAX_VALUE / 10 但将要加上的个位数 digit > 7，相加后也会溢出。
• 负数溢出：对于负数，我们同样用正数 sum 记录绝对值。判断逻辑类似，但边界是 8（因为 Integer.MIN_VALUE 的绝对值个位数是 8）。

代码实现：

public class Solution {
    public static int myAtoi(String str) {
        if (str == null) {
            return 0;
        }
        int i = 0;
        // 1. 跳过前导空格
        while (i < str.length() && str.charAt(i) == ' ') {
            i++;
        }
        // 2. 检查第一个非空字符是否有效
        if (i >= str.length() || (str.charAt(i) != '-' && str.charAt(i) != '+' && !(str.charAt(i) >= '0' && str.charAt(i) <= '9'))) {
            return 0;
        }
        // 3. 记录符号
        int sign = 1;
        if (i < str.length() && (str.charAt(i) == '-' || str.charAt(i) == '+')) {
            sign = str.charAt(i) == '-' ? -1 : 1;
            i++;
        }
        int sum = 0;
        // 4. 循环读取数字字符
        for (; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                int digit = str.charAt(i) - '0';
                // 溢出检查
                if (sign == 1) {
                    if (sum > Integer.MAX_VALUE / 10 || (sum == Integer.MAX_VALUE / 10 && digit > 7)) {
                        return Integer.MAX_VALUE;
                    }
                } else {
                    // 注意这里用正数判断负数的溢出，边界是8
                    if (sum > Integer.MAX_VALUE / 10 || (sum == Integer.MAX_VALUE / 10 && digit > 8)) {
                        return Integer.MIN_VALUE;
                    }
                }
                sum = sum * 10 + digit;
            } else {
                // 遇到非数字字符，立即结束
                return sum * sign;
            }
        }
        // 5. 返回最终结果
        return sum * sign;
    }
}

• 时间复杂度：O(n)，仅遍历字符串一次。
• 空间复杂度：O(1)，只使用了常数个额外变量。

方法二：正则表达式法

使用正则表达式可以简化字符串的模式匹配过程，使代码更加清晰。我们利用正则匹配出 可选符号位 + 连续数字 的模式子串，再对其进行转换和溢出判断。

代码实现：

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution {
    public int myAtoi(String s) {
        if (s == null) return 0;
        s = s.trim();
        if (s.length() == 0) return 0;

        // 使用正则表达式匹配“可选符号位+连续数字”的模式
        Pattern pattern = Pattern.compile("^[+-]?\\d+");
        Matcher matcher = pattern.matcher(s);

        if (!matcher.find()) {
            return 0; // 没有匹配到数字模式
        }

        String numStr = matcher.group();
        int sign = 1;
        int startIndex = 0;

        // 处理符号位
        if (numStr.charAt(0) == '+') {
            startIndex = 1;
        } else if (numStr.charAt(0) == '-') {
            sign = -1;
            startIndex = 1;
        }

        long result = 0; // 使用long类型中间变量，防止转换过程中溢出

        // 转换数字部分
        for (int i = startIndex; i < numStr.length(); i++) {
            int digit = numStr.charAt(i) - '0';
            result = result * 10 + digit;

            // 检查是否溢出int范围
            if (sign == 1 && result > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            // 在计算result时使用正数，判断负数溢出时与Integer.MIN_VALUE比较
            if (sign == -1 && -result < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
        }
        return (int) result * sign;
    }
}

• 时间复杂度：O(n)，trim()、正则匹配和数字转换均为线性时间。
• 空间复杂度：O(n)，需要存储匹配到的子字符串。

方法对比：

• 遍历法：效率更高，空间复杂度最优，能更细致地控制每一步逻辑，是面试中更受青睐的实现方式。
• 正则法：代码更简洁，可读性好，利用了Java内置的Integer类型和相关API，但在匹配失败时可能带来额外的性能开销。两种方法都需熟练掌握溢出判断这一核心考点。