0007. Reverse Integer ===================== 题目信息 -------- :题号: 0007. 整数反转 :难度: Medium :主题: 数学、整数、溢出边界 :原题: `LeetCode 0007 `_ :重点: 从文本反转和宽整数累积,推导到纯 32 位逐位处理,并在危险乘加发生前判断溢出 题目重述 -------- 给定一个 32 位有符号整数 ``x``,需要返回将其十进制数字顺序反转后的整数。负数只反转数字部分,负号仍保留在结果前;原整数末尾的零在反转后成为前导零,因此不会保留在整数结果中。 若反转后的数学结果超出 32 位有符号整数范围 ``[-2^31, 2^31 - 1]``,返回 ``0``。题目还要求不能依赖 64 位有符号或无符号整数保存中间结果。 自建示例 -------- * 普通正数:``x = 123``,依次取出 ``3``、``2``、``1``,返回 ``321``; * 负数含零:``x = -408``,数字部分反转后返回 ``-804``; * 末尾零:``x = 1200``,反转后的前导零被整数表示自动丢弃,返回 ``21``; * 正向溢出:``x = 1534236469``,反转结果超过 ``INT_MAX``,返回 ``0``; * 最小整数:``x = -2147483648``,不能先取绝对值,反转结果也越界,返回 ``0``; * 零值:``x = 0``,返回 ``0``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int reverseAsString(int x) { std::string text = std::to_string(x); const int firstDigit = text.front() == '-' ? 1 : 0; std::reverse(text.begin() + firstDigit, text.end()); const long long value = std::stoll(text); if (value < INT_MIN || value > INT_MAX) { return 0; } return static_cast(value); } int reverseWithWideInteger(int x) { long long remaining = x; long long reversed = 0; while (remaining != 0) { const long long digit = remaining % 10; remaining /= 10; reversed = reversed * 10 + digit; } if (reversed < INT_MIN || reversed > INT_MAX) { return 0; } return static_cast(reversed); } int reverseWithinInt(int x) { int reversed = 0; while (x != 0) { const int digit = x % 10; x /= 10; if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && digit > INT_MAX % 10)) { return 0; } if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && digit < INT_MIN % 10)) { return 0; } reversed = reversed * 10 + digit; } return reversed; } public: int reverse(int x) { return reverseWithinInt(x); } }; 题解 ---- 文本反转 ~~~~~~~~ 最直观的方法是把整数转换为十进制字符串,跳过开头的负号,反转剩余字符,再把文本解析回整数。原数末尾的零会移动到文本数字部分开头,重新解析时自然消失。 ``reverseAsString`` 直接对应题意,但需要 ``O(d)`` 字符串空间。更重要的是,反转后的文本可能已经超出 32 位范围,因此解析时仍需借助 ``long long``;它不能作为满足题目限制的主解法。 逐位转移 ~~~~~~~~ 字符串并非必要。十进制整数的最低位可以通过 ``digit = x % 10`` 取得,随后执行 ``x /= 10`` 删除该位。把取出的数字追加到结果末尾,则执行 ``reversed = reversed * 10 + digit``。 每轮完成一次明确的状态转移:输入少一个最低位,结果多一个新的最低位。循环结束时,原数字的各位已经按从低位到高位的顺序进入 ``reversed``,正好形成反转结果。 C++ 的有符号除法向零截断,余数与被除数同号。因此负数不需要单独提取符号:``-408 % 10`` 得到 ``-8``,后续数字依次为 ``0`` 和 ``-4``,累计结果自然成为 ``-804``。 这也避免了对 ``INT_MIN`` 取绝对值。``-2147483648`` 的正数绝对值是 ``2147483648``,已经超出 32 位有符号整数上界。 宽整数累积 ~~~~~~~~~~ ``reverseWithWideInteger`` 使用 ``long long`` 保存 ``remaining`` 和 ``reversed``,循环中可以直接执行乘十和加法,最后再判断结果是否位于 32 位范围。 这一步把字符串、解析和字符反转全部删除,只保留十进制数位转移。它的边界安全依赖更宽类型,而题目明确不允许用 64 位整数保存中间结果,因此还需要把越界判断移动到每次乘加之前。 乘加边界 ~~~~~~~~ 下一状态是 ``reversed * 10 + digit``。若先执行这条语句再检查,32 位有符号整数可能已经溢出,原数学结果也已经丢失。因此必须根据当前 ``reversed`` 预判下一次乘加是否安全。 正向上界分为三种情况: * ``reversed > INT_MAX / 10`` 时,单独乘十就会越界; * ``reversed < INT_MAX / 10`` 时,追加任意十进制位都安全; * ``reversed == INT_MAX / 10`` 时,``digit`` 不能大于 ``INT_MAX % 10``,即 ``7``。 负向下界完全对应: * ``reversed < INT_MIN / 10`` 时,乘十后会低于下界; * ``reversed > INT_MIN / 10`` 时,追加当前负数位仍安全; * ``reversed == INT_MIN / 10`` 时,``digit`` 不能小于 ``INT_MIN % 10``,即 ``-8``。 只有通过这两组检查后,``reversed = reversed * 10 + digit`` 才会执行。这样所有中间状态始终位于 32 位有符号整数范围内。 状态推演 ~~~~~~~~ 以 ``x = -408`` 为例: .. list-table:: :header-rows: 1 * - 轮次 - 原 ``x`` - ``digit`` - 新 ``x`` - 原 ``reversed`` - 新 ``reversed`` * - 1 - -408 - -8 - -40 - 0 - -8 * - 2 - -40 - 0 - -4 - -8 - -80 * - 3 - -4 - -4 - 0 - -80 - -804 对于 ``x = 1534236469``,处理到最后一个数字前,``reversed`` 已经是 ``964632435``。它大于 ``INT_MAX / 10``,算法在执行危险乘法前直接返回 ``0``。 代码演进 ~~~~~~~~ ``reverseAsString`` 按字符反转,代码需要字符串、负号起点、文本解析和额外空间。 ``reverseWithWideInteger`` 把字符操作替换为取余、整除和乘加,字符串与解析过程消失,但增加了 64 位中间状态和最终范围检查。 ``reverseWithinInt`` 保留相同的逐位转移,把最终检查前移到每次乘加之前。``long long`` 状态和循环后的范围判断同时消失,所有计算都在 ``int`` 中完成。 公开入口采用 ``reverseWithinInt``,因为它满足题目的存储限制,并且不会先触发有符号整数溢出再尝试补救。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要代价 * - 字符串反转 - ``O(d)`` - ``O(d)`` - 构造、反转并解析十进制文本 * - 宽整数逐位累积 - ``O(d)`` - ``O(1)`` - 使用 64 位中间结果后统一检查范围 * - 纯 32 位逐位处理 - ``O(d)`` - ``O(1)`` - 每次乘加前检查上下界 ``d`` 是输入的十进制位数。32 位整数最多只有常数个十进制位,但保留 ``O(d)`` 更能表达算法随位数增长的工作量。 边界处理 ~~~~~~~~ * ``x = 0`` 时循环不执行,初始结果 ``0`` 直接返回; * 原数末尾的零先被取出,追加到初始结果时不产生有效高位,因此自然消失; * 负数直接使用负余数累计,不取绝对值,可以安全处理 ``INT_MIN``; * 上下界判断使用 ``INT_MAX % 10`` 和 ``INT_MIN % 10``,不依赖硬编码末位; * 一旦下一次乘加会越界,立即返回 ``0``,不会执行未定义的有符号溢出。