Leetcode算法系列| 7. 整数反转

1.题目

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [?2^31, 2^31 ? 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

• 示例1:

输入：x = 123
输出：321

• 示例 2：

输入：x = -123
输出：-321

• 示例3：

输入：x = 120
输出：21

• 示例4：

输入：x = 0
输出：0

• 提示：
  • -2^31 <= x <= 2^31 - 1

2.题解

C# 解法一：数学

public class Solution {
    public int Reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < int.MinValue / 10 || rev > int.MaxValue / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
}

• 时间复杂度：O(log∣x∣)。翻转的次数即 x 十进制的位数。
• 空间复杂度：O(1)

Java 解法一：数学

• 思路同上

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
}

• 时间复杂度：O(log∣x∣)。翻转的次数即 x 十进制的位数。
• 空间复杂度：O(1)

Python3 解法一：数学

• 思路同上

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

• 时间复杂度：O(log∣x∣)。翻转的次数即 x 十进制的位数。
• 空间复杂度：O(1)