LeetCode: 7 Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2³¹, 2³¹ - 1], then return 0.

给定一个有符号的 32 位整数 x，返回将 x 的数字部分反转后的结果。如果反转后的整数超出了 32 位有符号整数的范围 [-2³¹, 2³¹ - 1]，则返回 0。

Example

Input: x = 123
Output: 321

Input: x = -123
Output: -321

Input: x = 120
Output: 21

Input: x = 0
Output: 0

Solution

Approach: Mathematical Reversal / 数学反转

To reverse the digits of an integer, we can repeatedly extract the last digit and build the reversed number step by step. This solution involves checking the sign of the number, reversing the absolute value of x, and finally reapplying the original sign.

Approach Explanation / 方法解释

Handle the Sign: First, determine if x is positive or negative and store its absolute value.
Extract and Reverse Digits: While x is not zero, extract the last digit and build the reversed number.
Check Overflow: Ensure that the reversed number does not exceed 32-bit integer limits.
Reapply the Sign: After reversing the digits, reapply the original sign.

Algorithm / 算法

Determine the sign of x and convert x to its absolute value.
While x is not zero:
- Extract the last digit: pop = x % 10.
- Remove the last digit from x: x //= 10.
- Before updating the reversed number, check if it will overflow.
- Update the reversed number: rev = rev * 10 + pop.
Return the reversed number multiplied by the original sign.

Implementation / 实现

Python

class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX = 2147483647  # Maximum 32-bit signed integer
        INT_MIN = -2147483648  # Minimum 32-bit signed integer

        rev = 0
        sign = 1 if x > 0 else -1  # Handle the sign of x
        x = abs(x)  # Work with the absolute value of x

        while x != 0:
            pop = x % 10  # Get the last digit
            x //= 10  # Remove the last digit by integer division

            # Check for overflow before multiplying rev by 10
            if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
                return 0

            rev = rev * 10 + pop  # Update the reversed number

        return rev * sign  # Restore the original sign

Explanation

Define Integer Limits / 定义整数限制
```
INT_MAX = 2147483647  # Maximum 32-bit signed integer
INT_MIN = -2147483648  # Minimum 32-bit signed integer
```
- English: Define the maximum and minimum values for a 32-bit signed integer.
- Chinese: 定义 32 位有符号整数的最大值和最小值。
Determine the Sign and Absolute Value / 确定符号和绝对值
```
sign = 1 if x > 0 else -1  # Handle the sign of x
x = abs(x)  # Work with the absolute value of x
```
- English: Determine the sign of x, and work with the absolute value of x to simplify the reversal process.
- Chinese: 确定 x 的符号，并使用 x 的绝对值进行反转，简化处理。
Iterate Through Digits / 逐位提取数字
```
while x != 0:
   pop = x % 10  # Get the last digit
   x //= 10  # Remove the last digit by integer division
```
- English: Continue processing digits by extracting the last digit of x and removing it using integer division.
- Chinese: 通过提取 x 的最后一位数字并使用整数除法移除，持续处理每一位数字。
Check for Overflow / 检查溢出
```
if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
   return 0
```
- English: Before multiplying rev by 10, check if it will overflow.
- Chinese: 在将 rev 乘以 10 之前，检查是否会发生溢出。
Append the Digit / 追加数字
```
rev = rev * 10 + pop  # Update the reversed number
```
- English: Update rev by appending the extracted digit to the reversed number.
- Chinese: 通过将提取的数字追加到反转后的数字，更新 rev。
Reapply the Original Sign / 重新应用原符号
```
return rev * sign  # Restore the original sign
```
- English: Multiply the reversed number by the original sign to return the final result.
- Chinese: 将反转后的数字乘以原来的符号以返回最终结果。

Complexity Analysis

Time Complexity / 时间复杂度: O(log₁₀(n)), where n is the input number. We process each digit once.
Space Complexity / 空间复杂度: O(1), since we only use a constant amount of space.

Key Concept

Digit Extraction / 数字提取: Extracting and appending digits allows us to reverse the integer.
Overflow Handling / 溢出处理: Careful checks are needed to ensure that the reversed number stays within the 32-bit signed integer range.

Summary

English: We reverse the digits of an integer by extracting and appending each digit while ensuring the result stays within the 32-bit signed integer range.
Chinese: 我们通过提取和追加每一位数字来反转整数，同时确保结果保持在 32 位有符号整数的范围内。

Tips

English: Always check for integer overflow when performing mathematical operations like multiplication or addition.
Chinese: 在进行诸如乘法或加法的数学运算时，务必检查整数溢出。

Warning

English: Be mindful of special cases like when the input is 0 or when reversing causes an overflow.
Chinese: 注意特殊情况，比如输入为 0 或者反转导致溢出时的情况。

5 More Similar Questions / 推荐5问题

Recommended Resources

English: Study other problems that involve reversing or manipulating digits to deepen your understanding of integer operations.
Chinese: 学习其他涉及反转或操作数字的问题，以加深对整数操作的理解。

Post Views: 49

CODEBITWAVE