018-字符串转换整数 (String to Integer)

题目描述

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

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−2³¹, 2³¹ − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2³¹ 的整数应该被固定为 −2³¹，大于 2³¹ − 1 的整数应该被固定为 2³¹ − 1。
返回整数作为最终结果。

注意：

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

示例

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 42 。

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 -42 。

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 4193 。

解题思路

按照题目要求的步骤逐步处理字符串：跳过前导空格、处理符号、读取数字、处理溢出。

JavaScript 解决方案

/**
 * @param {string} s
 * @return {number}
 */
const myAtoi = (s) => {
    const INT_MAX = Math.pow(2, 31) - 1;
    const INT_MIN = -Math.pow(2, 31);
    
    let i = 0;
    let sign = 1;
    let result = 0;
    
    // 1. 跳过前导空格
    while (i < s.length && s[i] === ' ') {
        i++;
    }
    
    // 2. 处理符号
    if (i < s.length && (s[i] === '+' || s[i] === '-')) {
        sign = s[i] === '-' ? -1 : 1;
        i++;
    }
    
    // 3. 读取数字
    while (i < s.length && s[i] >= '0' && s[i] <= '9') {
        const digit = parseInt(s[i]);
        
        // 检查溢出
        if (result > INT_MAX / 10 || (result === Math.floor(INT_MAX / 10) && digit > 7)) {
            return sign === 1 ? INT_MAX : INT_MIN;
        }
        
        result = result * 10 + digit;
        i++;
    }
    
    return sign * result;
};

复杂度分析

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

测试用例

// 测试函数
const testMyAtoi = () => {
    const testCases = [
        {
            s: "42",
            expected: 42
        },
        {
            s: "   -42",
            expected: -42
        },
        {
            s: "4193 with words",
            expected: 4193
        },
        {
            s: "words and 987",
            expected: 0
        },
        {
            s: "-91283472332",
            expected: -2147483648
        },
        {
            s: "91283472332",
            expected: 2147483647
        },
        {
            s: "3.14159",
            expected: 3
        },
        {
            s: "+1",
            expected: 1
        },
        {
            s: "   +0 123",
            expected: 0
        },
        {
            s: "00000-42a1234",
            expected: 0
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = myAtoi(testCase.s);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: s = "${testCase.s}"`);
        console.log(`期望: ${testCase.expected}, 实际: ${result}\n`);
    });
};

// 运行测试
testMyAtoi();

关键点总结

前导空格：跳过字符串开头的空格字符
符号处理：处理正负号，默认为正数
数字读取：只读取连续的数字字符
溢出检查：在每次乘以10之前检查是否会溢出
边界处理：对空字符串和无效输入的处理

总结

这道题考察了以下重点：

字符串处理：如何按照特定规则解析字符串
溢出处理：如何避免整数溢出
边界条件：对各种边界情况的处理
状态机：按照步骤逐步处理字符串

逐步解析法是最优解，时间复杂度为 O(n)，空间复杂度为 O(1)。在实际面试中，建议先理解题目要求，然后逐步实现每个步骤。

018-字符串转换整数 (String to Integer)

On this page