LeetCode 剑指 Offer 67. 把字符串转换成整数

约 6 分钟
文章信息 11 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 剑指 Offer 剑指 Offer（第 2 版） 腾讯 字节 亚马逊 百度
标签
字符串

题目描述

✅ 剑指 Offer 67. 把字符串转换成整数

image-20260928190556826

image-20260928190556827

image-20260928190556828

题意分析

按整数前缀解析规则把字符串转换为 32 位有符号整数：先跳过开头的普通空格，再读取至多一个可选正负号，随后读取连续数字，遇到第一个非数字就停止。

没有读取到数字时返回零，后续字符不需要全部合法，也不应跳过无效字符继续找数字。解析结果超过 [-2147483648, 2147483647] 时，返回对应的上下边界。

解法：按 atoi 规则模拟扫描

核心思路

[!blue]

用同一个下标按顺序完成空格、符号、数字三个阶段，阶段只前进、不回退。空格只允许在数字前的起始阶段跳过；可选符号最多读取一次；进入数字阶段后，再遇到符号、空格或字母都应立即结束。

用 sign 保存正负号，用 num 累积不带符号的数值大小。每读到数字 digit，执行 num = num * 10 + digit。没有读到数字时 num 保持零，空串、只有空格、只有符号以及首个有效字符并非数字的情况都自然返回零。

为防止在检查范围之前就发生 32 位溢出，num 使用 Java 的 long 或 Go 的 int64。每加入一位立刻检查：正数大于 2147483647 时返回上界；负数对应的带符号值小于 -2147483648 时返回下界。负下界的绝对值比正上界多一，因此不能把二者用同一个绝对值上限判断。

宽整数也不是无限大，安全性来自“逐位检查并立即返回”。只要上一轮没有结束，累计大小就不超过 32 位边界对应的绝对值；再乘十加一位仍远小于 64 位上限。越界后不会再继续读取任意长的数字串，所以不会积累到宽整数溢出。

越界后提前返回不会改变结果：后面若还是数字，只会继续扩大当前绝对值；若不是数字，解析本来也应停止，已有值仍然越界。最后若未超限，就按 sign 返回累计结果。

解题步骤

  1. 跳过开头的字符 ' '，始终先检查下标没有越界。
  2. 读取一次可选的 + 或 -，记录符号并推进下标。
  3. 连续读取 '0' 到 '9'，用宽整数逐位乘十加当前数字；遇其他字符立即停止。
  4. 每加一位检查正负对应边界，越界立即返回边界值。
  5. 扫描结束后返回带符号结果，没有数字则为零。

代码实现

class Solution {
    // 符号只能出现在数字之前，且只能读取一次。
    public int strToInt(String str) {
        if (str.length() == 0) {
            return 0;
        }

        int n = str.length();
        int i = 0;

        while (i < n && str.charAt(i) == ' ') {
            i++;
        }

        int sign = 1;

        // 符号只读取一次，后续再遇符号就由数字扫描结束。
        if (i < n && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
            if (str.charAt(i) == '-') {
                sign = -1;
            }

            i++;
        }

        long num = 0;

        while (i < n) {
            char c = str.charAt(i);

            if (c < '0' || c > '9') {
                break;
            }

            // 使用宽整数，加入每一位后立即检查返回范围。
            num = num * 10 + (c - '0');

            if (sign == 1 && num > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }

            // 负下界绝对值比正上界大一，按负数范围单独判断。
            if (sign == -1 && -num < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }

            i++;
        }

        return (int) (sign * num);
    }
}

func strToInt(str string) int {
    // 符号只能出现在数字之前，且只能读取一次。
    const intMax = 1<<31 - 1
    const intMin = -1 << 31

    if len(str) == 0 {
        return 0
    }

    i := 0

    for i < len(str) && str[i] == ' ' {
        i++
    }

    sign := 1
    // 符号只读取一次，后续再遇符号就由数字扫描结束。
    if i < len(str) && (str[i] == '+' || str[i] == '-') {
        if str[i] == '-' {
            sign = -1
        }
        i++
    }

    var num int64

    for i < len(str) {
        c := str[i]
        if c < '0' || c > '9' {
            break
        }

        // 使用宽整数，加入每一位后立即检查返回范围。
        num = num*10 + int64(c-'0')

        if sign == 1 && num > int64(intMax) {
            return intMax
        }
        // 负下界绝对值比正上界大一，按负数范围单独判断。
        if sign == -1 && -num < int64(intMin) {
            return intMin
        }

        i++
    }

    return int(num) * sign
}

复杂度分析

  • 时间复杂度：$O(n)$，下标只向右扫描，每个已处理字符只读取常量次，越界或遇非数字时可以提前结束。
  • 空间复杂度：$O(1)$，只维护下标、符号和一个宽整数累计值。

关键点总结

[!green]

  • 解析的是允许规则下的最长整数前缀，不是验证整串，也不是从任意位置提取数字。
  • 符号阶段最多执行一次，数字阶段遇非数字后不再恢复。
  • 逐位检查把累计值限制在可控范围内，宽整数负责安全容纳检查前的这一轮乘加。

易错点总结

[!yellow]

  • 把中间空格或字母跳过后继续拼接数字，会违反遇非数字立即停止的规则。
  • 允许重复读取正负号，会把本应无法开始数字解析的输入错误拼成整数。
  • 先用 32 位整数累积再检查，可能已经回绕，判断无法恢复正确值。
  • 把全部数字读完才检查，任意长数字串也可能超出 64 位范围。
  • 使用同一绝对值上限处理正负数，会错误拒绝合法的最小负整数或放过过大的正整数。

相似题目

题目 难度 关联与区别
65. 有效数字 困难 原题验证整串是否为合法数值，本题按atoi规则读取前缀并返回整数，停止规则不同。
7. 整数反转 中等 同样要在十进制累积过程中处理32位溢出，本题返回截断边界，反转题按题意返回0。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/74889191
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！