Mahdi Shamlou | 解题 LeetCode 第7题：整数反转 — 我的基于数学的反转，具备溢出安全

Source: Dev.to

大家好！我是 Mahdi Shamlou —— 继续我的 LeetCode 经典题目系列 🚀

在完成第 6 题 Zigzag Conversion 之后，今天我们来挑战第 7 题 —— Reverse Integer —— 这是一个非常常见的 Easy/Medium 题目，乍看很简单……直到你想起 32 位整数溢出的陷阱！

题目描述

给定一个有符号的 32 位整数 x，返回其数字反转后的结果。如果反转后 x 超出了有符号 32 位整数范围 [-2³¹, 2³¹ − 1]，则返回 0。

假设运行环境 不 支持 64 位整数。

示例

Input:  x = 123
Output: 321

Input:  x = -123
Output: -321

Input:  x = 120
Output: 21

Input:  x = 0
Output: 0

我的解法

逐位反转并进行溢出检查。我避免了字符串转换，而是使用数学方式——通过 % 10 取出数字，构建反转后的数，并在乘以 10 加上新数字之前检查是否会溢出。

class Solution:
    def reverse(self, x: int) -> int:
        reversed_x = 0

        # 先单独处理符号
        sign = 1 if x >= 0 else -1
        x = abs(x)

        while x > 0:
            digit = x % 10
            x //= 10

            # 在加入新数字前检查溢出
            # 2**31 - 1 = 2147483647
            # -2**31    = -2147483648
            if reversed_x > (2147483647 - digit) // 10:
                return 0
            if reversed_x < (-2147483648 + digit) // 10:
                return 0

            reversed_x = reversed_x * 10 + digit

        return sign * reversed_x

代码通过了所有测试用例，感觉很简洁，因为我们在真正发生溢出之前就捕获到了它。

你可以在我的仓库中找到所有解答：

GitHub – mahdi0shamlou/LeetCode: Solve LeetCode Problems

时间与空间复杂度

• 时间复杂度： O(log |x|) —— 每个数字只处理一次。
• 空间复杂度： O(1) —— 只使用了少量整数变量。

结果

提交后，溢出情况会正确返回 0，普通情况则能够完美反转。下面是成功提交的截图：