leetcodeday7 –整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

输入:x = 123
输出:321
示例 2:

输入:x = -123
输出:-321
示例 3:

输入:x = 120
输出:21
示例 4:

输入:x = 0
输出:0
 

提示:

-231 <= x <= 231 – 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题:这里首先想到的是先转字符串,然后反转字符串,但其实这种方法不能满足系统32位的限制。

因此参考官方解法,是一种纯数学方法,代码比较简单,但数学推导复杂:

记 rev 为翻转后的数字,为完成翻转,我们可以重复「弹出」x 的末尾数字,将其「推入」rev 的末尾,直至 x 为 0。

要在没有辅助栈或数组的帮助下「弹出」和「推入」数字,我们可以使用如下数学方法:

// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10

// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit

题目需要判断反转后的数字是否超过 3232 位有符号整数的范围 \([-2^{31},2^{31}-1]\),例如 x=2123456789x=2123456789 反转后的 \(\textit{rev}=9876543212>2^{31}-1=2147483647\),超过了 32 位有符号整数的范围。

因此我们需要在「推入」数字之前,判断是否满足

−231≤rev⋅10+digit≤231−1

若该不等式不成立则返回 0。

但是题目要求不允许使用 6464 位整数,即运算过程中的数字必须在 3232 位有符号整数的范围内,因此我们不能直接按照上述式子计算,需要另寻他路。

我们需要在「推入」数字之前,判断是否满足 :

$$
\left\lceil\frac{-2^{31}}{10}\right\rceil \leq \operatorname{rev} \leq\left\lfloor\frac{2^{31}-1}{10}\right\rfloor
$$

是否成立,若不成立则返回 0

# @lc code=start
class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1

        rev = 0
        while x != 0:
            # INT_MIN 也是一个负数,不能写成 rev < INT_MIN // 10
            if rev < INT_MIN // 10 + 1 or rev > INT_MAX // 10:
                return 0
            digit = x % 10
            # Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果,因此这里需要进行特殊判断
            if x < 0 and digit > 0:
                digit -= 10

            # 同理,Python3 的整数除法在 x 为负数时会向下(更小的负数)取整,因此不能写成 x //= 10
            x = (x - digit) // 10
            rev = rev * 10 + digit
        
        return rev

        # @lc code=end

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注