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

游戏开发小Y

发布于 2024-01-18 19:29:00

770

发布于 2024-01-18 19:29:00

文章被收录于专栏：Unity开发系列专栏Unity开发系列专栏

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