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

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

题目描述

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

题意分析

给一个字符串，从左往右尽可能读出一个 32 位有符号整数并返回。注意这不是「校验字符串是否合法」，而是「能读多少读多少」：读到不认识的字符就停下，把已经读到的部分当作答案；一个数字都没读到就返回 0。

规则本身透露了算法信号。字符只有四类——空格、符号、数字、其他，而且它们出现的先后顺序是固定的：前导空格只能在最前面，符号只能紧跟在空格之后、数字之前，数字之后一旦出现别的字符就结束。四类字符构成一条单向的消费链，任何一段结束后都不会再回头，所以整件事只需要一次从左到右的扫描，既不需要回溯，也不需要把字符串切成 token 再处理。

另一个信号是返回类型是 32 位整数，而输入串的长度没有对应限制。也就是说输入完全可以携带一个 20 位甚至 200 位的数字，越界处理不是可选项，而是主逻辑的一部分。

边界要在动手前列全：空串；全是空格；只有一个 + 或 - 后面没有数字；数字前面夹了别的字符（如 "words 123"）；数字中间夹空格（如 "1 2"）；连续两个符号（如 "+-12"）；以及正负两侧不对称的极值 $2147483647$ 与 $-2147483648$。

解法：按 atoi 规则模拟扫描

核心思路

最直觉的写法是先用正则或者 split 把「符号 + 数字」那一段抠出来，再交给库函数转成整数。瓶颈有两个：抠取本身就要把上面那套规则实现一遍，等于没省事；而且库函数遇到超长数字会抛异常或直接回绕，越界仍然得自己兜住。既然规则最终还是要手写，就没必要多切一趟字符串。

换个角度看这些规则：它们描述的是一个不会回头的指针。指针先停在空格段的末尾，再跨过至多一个符号，然后停在数字段的末尾。每一段都只需要一个 while，段与段之间不共享状态，唯一需要跨段传递的只有符号和累积值。

于是可以写出扫描的不变量：当下标走到 i 时，sign 是已经锁定的符号（没有显式符号则为 1），num 恰好等于「数字段起点到 i 之间」这串十进制字符所表示的数值。每读入一位数字 d，不变量的维持方式就是 num = num * 10 + d。

越界处理挂在这条不变量上。把 num 声明成 64 位是关键：由于每读一位都立刻判一次界，num 在被判定越界之前最大也就是 $2147483647$，再乘 10 加 9 后不超过 $2.2 \times 10^{10}$，离 64 位的上界还差得远，所以 num 自身永远不会溢出，越界判定退化成一次普通的大小比较。

正负必须分开判，因为区间 $[-2^{31}, 2^{31}-1]$ 两端不对称：$2147483648$ 对正数来说已经超界，对负数来说恰好是合法的下界。

解题步骤

  • 空串直接返回 0：这一行其实是冗余的，后面所有循环条件都带 i < n，空串会自然走到返回语句。写出来只是让「读不到数字就是 0」这个语义更显眼。
  • 跳过前导空格：while (i < n && str.charAt(i) == ' ') i++。只跳半角空格，不要顺手把制表符、换行也跳掉——题目只把空格定义为可忽略字符，跳多了会让本该返回 0 的输入返回出数字。
  • 读符号，且只读一次：命中 + 或 - 时记录 sign 并把 i 前移。之所以不放进循环，是因为符号出现第二次就属于「其他字符」，应该终止解析；不写循环，第二个符号自然会落进下面数字循环的 break。
  • 逐位累积数字：num = num * 10 + (c - '0')，遇到非数字立刻 break 而不是 continue，因为规则要求的是「停止」而不是「跳过」。
  • 每加一位判一次界：正号看 num > Integer.MAX_VALUE，负号看 -num < Integer.MIN_VALUE。判定必须放在循环体内、紧跟累积之后；挪到循环外就等于让 num 先把整串数字吃完，再长的输入都会把 64 位撑爆。
  • 返回 (int) (sign * num)：走到这里 num 一定在 int 范围内，强转安全。若数字循环一次都没进（全空格、只有符号、开头就是别的字符），num 保持 0，返回值自然是 0，不需要任何特判。

以 " -042a5" 走一遍（n = 7）：

  • 初始：i = 0、sign = 1、num = 0
  • i = 0，字符是空格 → 跳过，i = 1
  • i = 1，字符是空格 → 跳过，i = 2
  • i = 2，字符是 - → sign = -1，i = 3；符号段就此结束，后面再遇到符号也不会被采纳
  • i = 3，字符 0 → num = 0 * 10 + 0 = 0，未越界，i = 4；前导零不用特殊处理，乘 10 加 0 恒等于 0
  • i = 4，字符 4 → num = 0 * 10 + 4 = 4，i = 5
  • i = 5，字符 2 → num = 4 * 10 + 2 = 42，i = 6
  • i = 6，字符 a → 非数字，break，后面的 5 被彻底丢弃
  • 返回 sign * num = -42

再用 "2147483648" 检验越界分支：前 9 位累积出 num = 214748364，读到第 10 位时 num = 2147483648，大于 Integer.MAX_VALUE，函数立刻返回 2147483647。如果把 num 声明成 int，这一步会回绕成 -2147483648，num > Integer.MAX_VALUE 恒为假，判定形同虚设，最终返回一个负数。

代码实现

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)$，三段扫描共用同一个下标 i，i 只增不减，每个字符至多被读一次，循环体内全是常数操作。
  • 空间复杂度：$O(1)$，只用了下标、符号、累积值三个标量，与字符串长度无关；没有建任何中间数组或子串。

关键点总结

  • 规则型模拟题的骨架是「把字符分类 + 确定各类的出现顺序」，顺序一旦是全序，就能用一次不回头的扫描消化掉；面试时先把这两件事说清楚再写代码，面试官真正在看的是规则有没有被枚举完整。
  • 用 64 位承接累积值，把溢出检测降级成一次比较。若面试官额外限制「只能用 32 位」，备选答案是提前判断 num > (Integer.MAX_VALUE - d) / 10，即在乘 10 之前反推，能主动说出这条通常是加分项。
  • 越界检查必须逐位进行。只要每位都判，累积值就永远处在「至多超界一个数量级」的范围内，这是 64 位不会溢出的理由，而不是运气。
  • 有符号整数的正负区间不对称，$-2147483648$ 没有对应的正数，所以两侧要分开判定。
  • 返回 0 的几种场景（空串、全空格、孤立符号、开头是别的字符）应该由「数字循环一次都没进」统一覆盖，而不是堆特判——特判越多，遗漏越多。

易错点总结

  • 用 int 累积：输入 "2147483648" 时第 10 位加完已经回绕成负数，num > Integer.MAX_VALUE 恒为假，函数返回 -2147483648 而不是 2147483647。
  • 把越界判断挪到循环外：输入 100 个 9 时，即便用 long 累积也会在中途溢出成一个不可预测的值，返回结果完全随机。
  • 只写 num > Integer.MAX_VALUE 一条判定、最后再乘符号：输入 "-2147483648" 会在最后一位触发上界分支，返回 2147483647，而正确答案恰好是合法的 -2147483648。
  • 用 Character.isWhitespace 跳前导空格：输入 "\t123" 应当返回 0（制表符不是可忽略字符），却会被跳过并返回 123。
  • 把读符号写成循环：输入 "+-12" 应当返回 0，连读两个符号后会返回 -12。
  • 遇到空格就跳过继续扫数字：输入 "1 2" 应当返回 1，把中间空格当无关字符会拼成 12。
  • 非数字时用 continue 而不是 break：输入 "12a34" 应当返回 12，继续扫描会得到 1234。
  • 跳完空格后不带 i < n 就取字符：输入 " "（全是空格）会直接抛出下标越界异常。
  • 直接调用 Integer.parseInt / strconv.Atoi 兜底：输入 "words and 987" 会抛异常，输入 "42abc" 也会失败，得包一层 try-catch 再手工截断——绕过了本题的全部考点，面试中基本等于没做。

相似题目

题目 难度 考察点
8. 字符串转换整数 (atoi) 中等 与本题规则逐条相同，只是题面措辞与函数名不同，可直接套用
65. 有效数字 困难 只判合法性不求值，还要接受小数点与科学计数法 e，字符分类多出一倍
剑指 Offer 20. 表示数值的字符串 中等 同为判定题，允许首尾空格但不允许中间空格，需要显式的状态迁移表
7. 整数反转 中等 数字已经给出，难点只剩反转过程中的溢出判定，且通常不允许借助 64 位
165. 比较版本号 中等 同样逐段解析数字，但要按 . 切分并逐段比较，前导零无意义
13. 罗马数字转整数 简单 也是字符串转数值，累积规则改成看相邻两位的大小决定加还是减