算法学习

Appearance

8. 字符串转换整数 (atoi) Medium ​

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

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

  • 空格：读入字符串并丢弃无用的前导空格（" "）
  • 符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
  • 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
  • 舍入：如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1 。

返回整数作为最终结果。

示例 1:
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
带下划线线的字符是所读的内容，插入符号是当前读入位置。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
第 3 步："42"（读入 "42"）

示例 2:
输入：s = " -042"
输出：-42
解释：
第 1 步：" -042"（读入前导空格，但忽视掉）
第 2 步：" -042"（读入 '-' 字符，所以结果应该是负数）
第 3 步：" -042"（读入 "042"，在结果中忽略前导零）

示例 3:
输入：s = "1337c0d3"
输出：1337
解释：
第 1 步："1337c0d3"（当前没有读入字符，因为没有前导空格）
第 2 步："1337c0d3"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
第 3 步："1337c0d3"（读入 "1337"；由于下一个字符不是一个数字，所以读入停止）

示例 4:
输入：s = "0-1"
输出：0
解释：
第 1 步："0-1" (当前没有读入字符，因为没有前导空格)
第 2 步："0-1" (当前没有读入字符，因为这里不存在 '-' 或者 '+')
第 3 步："0-1" (读入 "0"；由于下一个字符不是一个数字，所以读入停止)

示例 5:
输入：s = "words and 987"
输出：0
解释：
读取在第一个非数字字符“w”处停止。

解题思路 ​

输入： 一个字符串 s

输出： 实现一个函数将字符串 s 转化成 4 个字节的数字

本题属于字符串问题。

  1. 跳过前导空格
  2. 处理符号位
  3. 读取数字
    • num = num * 10 + 当前数字
  4. 防止溢出
    • 对正数：num > (INT_MAX - digit) / 10
    • 对负数：num > (INT_MAX + 1 - digit) / 10
  5. 返回结果

代码实现 ​

python
class Solution:
    def myAtoi(self, s: str) -> int:
        # 题目要求的 32 位整数范围
        MAX_INT = 2 ** 31 - 1   # 2147483647
        MIN_INT = -2 ** 31      # -2147483648

        i, n = 0, len(s)

        # 1. 跳过前导空格
        while i < n and s[i] == ' ':
            i += 1
        # 如果全是空格，直接返回 0
        if i == n:
            return 0

        # 2. 读取符号位（+ 或 -）
        sign = 1
        if s[i] == '-' or s[i] == '+':
            sign = -1 if s[i] == '-' else 1
            i += 1

        # 3. 读取连续的数字字符，并构建结果
        num = 0
        while i < n and '0' <= s[i] <= '9':
            digit = int(s[i])  # 当前数字

            # 4. 溢出判断（提前检查，避免 num*10 后超范围）
            if sign == 1 and num > (MAX_INT - digit) // 10:
                return MAX_INT
            if sign == -1 and num > (MAX_INT + 1 - digit) // 10:
                return MIN_INT

            # 累积结果
            num = num * 10 + digit
            i += 1

        # 5. 返回带符号的结果
        return sign * num
javascript
/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
    // 32 位有符号整数范围
    const MAX = 2 ** 31 - 1;   // 2147483647
    const MIN = -(2 ** 31);    // -2147483648

    let i = 0;  // 当前扫描指针
    
    // 1. 跳过前导空格
    while (i < s.length && s[i] === ' ') i++;
    // 如果跳过空格后已经到末尾，直接返回 0
    if (i == s.length) return 0;

    // 2. 读取符号位（+ 或 -）
    let sign = 1;
    if (s[i] === '-' || s[i] === '+') {
        sign = s[i] === '-' ? -1 : 1;
        i++;
    }

    // 3. 读取连续的数字字符
    let num = 0;
    while (i < s.length && /[0-9]/.test(s[i])) {
        const d = Number(s[i]);  // 当前字符转为数字

        // 4. 溢出判断（提前检查是否会超过范围）
        if (sign === 1 && num > (MAX - d) / 10) return MAX;
        if (sign === -1 && num > (MAX + 1 - d) / 10) return MIN;

        // 累积结果
        num = num * 10 + d;
        i++;
    }

    // 5. 返回最终结果（符号 * 数字）
    return sign * num;
};

复杂度分析 ​

时间复杂度：O(n)

空间复杂度：O(1)

链接 ​

8 国际版

8 中文版