Medium

题目描述

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

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

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

示例 1：

输入：x = 123
输出：321

示例 2：

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

示例 3：

输入：x = 120
输出：21

提示：

  • -2³¹ <= x <= 2³¹ - 1

解题思路

解题思路

这道题要求反转一个32位有符号整数的数字部分，关键在于处理溢出问题。

主要思路：

  1. 逐位反转：通过 x % 10 获取最低位数字，通过 x / 10 去掉最低位，同时构建反转后的数字
  2. 溢出检测：由于不能使用64位整数，需要在每次操作前检查是否会溢出

溢出检测策略：

  • 32位整数范围：[-2147483648, 2147483647]
  • 在执行 result = result * 10 + digit 之前，检查：
    • 如果 result > INT_MAX / 10，则必定溢出
    • 如果 result == INT_MAX / 10，则需要检查当前数字是否超过 INT_MAX % 10
    • 负数情况类似处理

处理细节：

  • 负数的符号在C++中取模运算会保持，所以处理逻辑统一
  • 末尾的0会自然消失（如120变成21）

这种方法时间复杂度为O(log n)，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;
            
            // 检查正溢出
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) {
                return 0;
            }
            // 检查负溢出
            if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) {
                return 0;
            }
            
            result = result * 10 + digit;
        }
        return result;
    }
};

class Solution:
    def reverse(self, x: int) -> int:
        # Python中整数范围
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        
        result = 0
        # 处理负数
        sign = -1 if x < 0 else 1
        x = abs(x)
        
        while x != 0:
            digit = x % 10
            x //= 10
            
            # 检查溢出
            if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > 7):
                return 0
            
            result = result * 10 + digit
        
        result *= sign
        
        # 最终检查范围
        if result < INT_MIN or result > INT_MAX:
            return 0
        
        return result

public class Solution {
    public int Reverse(int x) {
        int result = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;
            
            // 检查正溢出
            if (result > int.MaxValue / 10 || (result == int.MaxValue / 10 && digit > 7)) {
                return 0;
            }
            // 检查负溢出
            if (result < int.MinValue / 10 || (result == int.MinValue / 10 && digit < -8)) {
                return 0;
            }
            
            result = result * 10 + digit;
        }
        return result;
    }
}

var reverse = function(x) {
    const isNegative = x < 0;
    x = Math.abs(x);
    
    let reversed = 0;
    while (x > 0) {
        reversed = reversed * 10 + x % 10;
        x = Math.floor(x / 10);
    }
    
    reversed = isNegative ? -reversed : reversed;
    
    if (reversed < Math.pow(-2, 31) || reversed > Math.pow(2, 31) - 1) {
        return 0;
    }
    
    return reversed;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)n为输入整数的绝对值，需要处理的位数为log₁₀(n)
空间复杂度O(1)只使用了常数级别的额外空间

相关题目