LeetCode 0008: String to Integer (atoi)

题目描述

实现一个 atoi 函数，使其能将字符串转换成一个 32 位有符号整数。

解题思路

去除前导空格：跳过字符串前面的所有空格字符。
处理符号位：检查下一个字符是否为 + 或 -，确定最终结果的符号。
读取数字：逐个字符读取数字部分，直到遇到非数字字符或字符串结束。
处理溢出：如果数值超出 32 位有符号整数范围，返回 INT_MAX (2³¹ − 1) 或 INT_MIN (−2³¹)。

代码实现

public int myAtoi(String s) {
    int index = 0;
    int sign = 1;
    int result = 0;
    int n = s.length();

    // 去除前导空格
    while (index < n && s.charAt(index) == ' ') {
        index++;
    }

    // 处理符号位
    if (index < n && (s.charAt(index) == '+' || s.charAt(index) == '-')) {
        sign = s.charAt(index) == '-' ? -1 : 1;
        index++;
    }

    // 读取数字
    while (index < n && Character.isDigit(s.charAt(index))) {
        int digit = s.charAt(index) - '0';
        // 检查溢出
        if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        result = result * 10 + digit;
        index++;
    }

    return result * sign;
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。
空间复杂度：O(1)，仅使用了常数空间。

示例

输入: "42"
输出: 42

输入: "   -42"
输出: -42

输入: "4193 with words"
输出: 4193

流程图

graph TD
    A[开始] --> B[去除前导空格]
    B --> C[处理符号位]
    C --> D[读取数字]
    D --> E[检查溢出]
    E --> F[返回结果]

总结

本题的关键在于处理字符串的边界条件，如空格、符号位和溢出情况。通过逐步解析字符串，可以高效地实现 atoi 函数。