逆整数（Leetcode）

Question

我试图在 leetcode 上解决 7.Reverse Integer https://leetcode.com/problems/reverse-integer/.

给定一个带符号的 32 位整数 x，返回 x 的数字反转。如果反转 x 导致值超出有符号 32 位整数范围 [-2^31, 2^31 - 1]，则返回 0。

示例1：

Input: x = 123  
Output: 321

我针对上述问题的解决方案是

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

我错了 4 个测试用例。其中之一是：

示例

Input: 1534236469  
Output : 1056389759  
Expected: 0  

Answer 1

你的问题是溢出在

num

变量中，而你没有检查它。通过在执行

num = num * 10 + a

之前添加检查以确保计算不会溢出，您可以在必要时返回

0

。

此外，您没有正确处理负数。预先检查负数可以让您使用正数，然后对结果求负。

class Solution {  
    public int reverse(int x) {  
        int num = 0;  
        Boolean negative = false;
        
        if (x == Integer.MIN_VALUE) return 0;
        if (x < 0) {
            x = -x;
            negative = true;
        }
        while (x != 0) {  
            int a = x % 10; 
            // Check if the next operation is going to cause an overflow
            // and return 0 if it does
            if (num > (Integer.MAX_VALUE - a) / 10) return 0;
            num = num * 10 + a;  
            x = x / 10;  
        }  
        return negative ? -num : num;  
    }  
} 

Answer 2

您没有处理循环中可能发生的理论有符号 32 位整数溢出，这意味着您有时会返回超出该范围的数字。此外，对于负值，逻辑将无法按预期工作。

为了真正精确地了解有符号 32 位整数的限制，当输入为 -2³¹ 时需要特别小心，因为它的绝对值不代表有效的有符号 32 位整数。

class Solution {
    public int reverse(int x) {
        if (x < 0) return x == -2147483648 ? 0 : -reverse(-x);
        int res = 0;
        while (x > 0 && res < 214748364) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return x == 0 ? res
             : res > 214748364 || x > 7 ? 0
             : res * 10 + x;
    }
}

Answer 3

您选择的方法并不遥远。

1. 您当前检查输入

   x

   是否在无符号整数范围内。但他们要求检查 x-reversed。
2. 您将答案汇总为一个整数，因此您可能会溢出而不被注意到。

如果您将结果

num

聚合到 long 类型的变量中，并且如果反转后超出了 unsigned int 的范围，则拒绝/清零答案，那么您的两个问题都可以得到解决。

您也可以使用 Math.addExact(a, b)、Math.multiplyExact(a,b) 和 try-catch 在溢出时立即退出。

Answer 4

输入：123 输出：321 输入：-123 输出：-321 输入：120 输出：2

类解决方案{ 民众： int 反向(int x) {

    int rev = 0;

    constexpr int top_limit = INT_MAX/10;

    constexpr int bottom_limit = INT_MIN/10;

    while (x) {

        if (rev > top_limit || rev < bottom_limit)

            return 0;

        rev = rev * 10 + x % 10;

        x /= 10;
    }
    return rev;
}

};