0008. String to Integer (atoi) ============================== 题目信息 -------- :题号: 0008. 字符串转换整数(atoi) :难度: Medium :主题: 字符串、解析、状态机、溢出边界 :原题: `LeetCode 0008 `_ :重点: 把前缀语法拆成空格、符号和数字三个阶段,并用负数累积覆盖不对称的 32 位边界 题目重述 -------- 给定字符串 ``s``,需要按照固定规则解析其开头,并返回一个 32 位有符号整数: #. 跳过开头连续出现的普通空格; #. 读取至多一个 ``+`` 或 ``-`` 作为符号; #. 从当前位置连续读取十进制数字,遇到第一个非数字字符时停止; #. 若没有读取到数字,返回 ``0``; #. 若解析结果小于 ``-2^31``,返回 ``-2^31``;若大于 ``2^31 - 1``,返回 ``2^31 - 1``。 这里只识别字符串开头的合法前缀,不会越过无效字符继续寻找数字。字符串长度位于 ``[0, 200]``,可能包含英文字母、数字、空格、``+``、``-`` 和 ``.``。 自建示例 -------- * 普通正数:``s = "42"``,返回 ``42``; * 空格、符号和前导零:``s = " -001204x7"``,在 ``x`` 处停止,返回 ``-1204``; * 非数字截断:``s = "4193 with words"``,只读取连续数字前缀,返回 ``4193``; * 无效开头:``s = "words and 987"``,第一个非空格字符不是符号或数字,返回 ``0``; * 符号后为空格:``s = " + 17"``,符号后没有立即出现数字,返回 ``0``; * 重复符号:``s = "--12"``,第二个符号终止数字读取,返回 ``0``; * 正向溢出:``s = "91283472332"``,返回 ``2147483647``; * 负向溢出:``s = "-91283472332"``,返回 ``-2147483648``; * 空字符串:``s = ""``,返回 ``0``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: int scanWithWideInteger(const std::string& s) { int index = 0; while (index < static_cast(s.size()) && s[index] == ' ') { ++index; } int sign = 1; if (index < static_cast(s.size()) && (s[index] == '+' || s[index] == '-')) { sign = s[index] == '-' ? -1 : 1; ++index; } long long value = 0; while (index < static_cast(s.size()) && s[index] >= '0' && s[index] <= '9') { value = value * 10 + s[index] - '0'; if (sign == 1 && value > INT_MAX) { return INT_MAX; } if (sign == -1 && -value < INT_MIN) { return INT_MIN; } ++index; } return static_cast(sign * value); } int scanWithinInt(const std::string& s) { int index = 0; while (index < static_cast(s.size()) && s[index] == ' ') { ++index; } int sign = 1; if (index < static_cast(s.size()) && (s[index] == '+' || s[index] == '-')) { sign = s[index] == '-' ? -1 : 1; ++index; } const int limit = sign == -1 ? INT_MIN : -INT_MAX; int value = 0; while (index < static_cast(s.size()) && s[index] >= '0' && s[index] <= '9') { const int digit = s[index] - '0'; if (value < limit / 10 || (value == limit / 10 && -digit < limit % 10)) { return sign == -1 ? INT_MIN : INT_MAX; } value = value * 10 - digit; ++index; } return sign == -1 ? value : -value; } public: int myAtoi(std::string s) { return scanWithinInt(s); } }; 题解 ---- 前缀语法 ~~~~~~~~ 本题不是在字符串任意位置搜索整数,而是识别从下标 ``0`` 开始的一段固定前缀。合法字符顺序只能是 ``若干空格 → 可选符号 → 连续数字``。 三个阶段一旦离开就不会返回: * 空格阶段结束后,后续空格会直接终止数字读取; * 符号阶段最多消费一个字符,第二个符号不会被接受; * 数字阶段遇到第一个非数字字符后立即停止,后面的字符全部忽略。 因此 ``"words 42"`` 返回 ``0``,而 ``"42words17"`` 返回 ``42``。解析指针始终只向右移动,不需要回溯。 宽整数累积 ~~~~~~~~~~ 最直接的整数实现是把符号与绝对值分开。数字阶段每读取一个 ``digit``,执行 ``value = value * 10 + digit``,把已有数字左移一位并追加当前数字。 ``scanWithWideInteger`` 使用 ``long long`` 保存 ``value``,因此可以先完成当前乘加,再与 ``INT_MAX`` 或 ``INT_MIN`` 比较并钳制。它删除了字符缓冲区和二次转换,只保留一次顺序扫描。 这版代码清楚,但边界安全依赖更宽整数。为了让中间状态始终保持在 32 位范围内,需要在乘十和追加数字之前完成判断。 负数累积 ~~~~~~~~ 32 位有符号范围并不对称:``INT_MAX`` 是 ``2147483647``,``INT_MIN`` 是 ``-2147483648``。若始终累积非负绝对值,负数最小值的绝对值无法放入 ``int``。 主解法让 ``value`` 始终非正,每次执行 ``value = value * 10 - digit``。正数最终返回 ``-value``,负数直接返回 ``value``。这样两种符号的中间值都能落在 ``int`` 范围内,包括 ``INT_MIN``。 根据符号选择允许的最小值: * 负数使用 ``limit = INT_MIN``; * 正数使用 ``limit = -INT_MAX``。 两种情况都转化为同一个要求:追加数字后的 ``value`` 不能小于 ``limit``。 乘减边界 ~~~~~~~~ 下一状态为 ``value * 10 - digit``。危险运算发生前,先比较 ``value`` 与 ``limit / 10``: * ``value < limit / 10`` 时,单独乘十就会低于边界; * ``value > limit / 10`` 时,本次追加一定安全; * 两者相等时,需要继续比较最后一位,要求 ``-digit >= limit % 10``。 因此越界条件统一为 ``value < limit / 10 || (value == limit / 10 && -digit < limit % 10)``。 正数对应的负边界是 ``-2147483647``,最后一位限制为 ``-7``;负数边界是 ``-2147483648``,最后一位限制为 ``-8``。同一段判断自然覆盖两侧钳制。 状态推演 ~~~~~~~~ 以 ``s = " -001204x7"`` 为例: .. list-table:: :header-rows: 1 * - 阶段 - 字符 - ``sign`` - 原 ``value`` - 新 ``value`` - 动作 * - 空格 - 三个空格 - 1 - 0 - 0 - 移动到负号 * - 符号 - ``-`` - -1 - 0 - 0 - 记录负号 * - 数字 - ``0, 0, 1, 2, 0, 4`` - -1 - 0 - -1204 - 逐位乘十减数字 * - 停止 - ``x`` - -1 - -1204 - -1204 - 结束解析 负号输入直接返回 ``value = -1204``。后面的 ``7`` 位于第一个非数字字符之后,不再参与解析。 代码演进 ~~~~~~~~ ``scanWithWideInteger`` 把解析分成空格、符号和数字三个顺序阶段,使用一次循环累积数字,并依靠 ``long long`` 在更新后检查范围。 ``scanWithinInt`` 保留相同的前缀扫描结构,把正绝对值改为负数累积。宽整数和更新后的范围检查消失,替换为乘减之前的统一边界判断。 公开入口采用 ``scanWithinInt``。它只扫描有效前缀,使用 ``O(1)`` 状态,并在所有中间步骤中保持 32 位安全。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 边界策略 * - 宽整数累积 - ``O(n)`` - ``O(1)`` - 使用 64 位中间值后钳制 * - 负数累积 - ``O(n)`` - ``O(1)`` - 在 32 位乘减前预判边界 两种方法都只访问从字符串开头到第一个无效字符之间的内容,最坏扫描整个字符串。主解法不创建子串、字符数组或额外状态表。 边界处理 ~~~~~~~~ * 只跳过普通空格 ``' '``,不会把其他字符当作前导空白; * 字符串结束、只有空格或只有符号时,数字循环不执行,返回 ``0``; * 符号后必须立即出现数字,否则结果为 ``0``; * 数字前导零只会重复执行 ``value = value * 10``,不会改变结果; * 遇到第一个非数字字符立即停止,不会在后续位置重新寻找数字; * 越界判断发生在乘十和减数字之前,避免 32 位有符号整数溢出。