LeetCode【0007】整数反转
本文目录
- 1 中文题目
- 2 求解思路
- 2.1 基础解法：字符串反转法
- 2.2 优化解法：利用栈特性
- 2.3 最优解法：位运算法
- 3 题目总结
1 中文题目
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围
[
−
2
31
,
2
31
−
1
]
[−2^{31}, 2^{31} − 1]
[−231,231−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^{31} \leq x \leq 2^{31} − 1
−231≤x≤231−1
2 求解思路
2.1 基础解法：字符串反转法
思路
将数字转化为字符串，利用字符串的反转去实现。示例：
# 例如：x = -123
# 步骤1：提取符号 → sign = -1, x = 123
# 步骤2：转为字符串 → "123"
# 步骤3：反转字符串 → "321"
# 步骤4：转回整数并添加符号 → -321
# 步骤5：判断数字是否满足条件
Python代码
class Solution:
def reverse(self, x: int) -> int:
"""
整数反转 - 字符串反转法
参数：
x: 待反转的整数
返回：
反转后的整数，如果溢出返回0
思路：
1. 处理符号
2. 转换为字符串并反转
3. 转回整数并处理溢出
"""
# 处理0的情况
if x == 0:
return 0
# 保存符号并转为正数处理
is_negative = x < 0
x = abs(x)
# 转为字符串并反转
reversed_str = str(x)[::-1]
# 转回整数
result = int(reversed_str)
# 还原符号
if is_negative:
result = -result
# 处理溢出情况
# 32位有符号整数范围：[-2^31, 2^31 - 1]
if result < -2**31 or result > 2**31 - 1:
return 0
return result
时空复杂度分析
- 时间复杂度：
O(log|x|)- 转换为字符串：
O(log|x|) - 字符串反转：
O(log|x|) - 转回整数：
O(log|x|)
总体时间复杂度：O(log|x|)
- 转换为字符串：
- 空间复杂度：
O(log|x|)- 需要存储字符串：
O(log|x|) - 其他变量：
O(1)
- 需要存储字符串：
2.2 优化解法：利用栈特性
思路
将整数的每一位依次入栈，然后出栈重建，利用栈的先进后出特性自然实现数字的反转。
- 数字分解和入栈
- 分解过程
- 使用求余运算(%)获取个位数
- 使用整除运算(//)去除个位数
- 重复此过程直到数字变为0
- 入栈顺序
- 从个位开始入栈
- 依次存储每一位数字
- 分解过程
- 重建数字
- 出栈过程
- 从栈顶开始取数
- 每次取出一个数字后乘以10加上新数字
- 出栈过程
python代码
from collections import deque
class Solution:
def reverse(self, x: int) -> int:
"""
使用deque实现栈方法的整数反转
参数：
x: 输入的整数
返回：
反转后的整数，如果溢出返回0
"""
# 定义32位整数的范围
MAX_INT = 2**31 - 1 # 2147483647
MIN_INT = -2**31 # -2147483648
# 特殊情况处理
if x == 0:
return 0
# 符号处理
sign = -1 if x < 0 else 1
x = abs(x)
# 创建双端队列作为栈
stack = deque()
# 分解数字并入栈
while x > 0:
stack.append(x % 10) # 入栈操作
x //= 10
# 出栈重建数字
result = 0
while stack:
# 溢出检查
if result > MAX_INT // 10:
return 0
if result == MAX_INT // 10 and stack[0] > MAX_INT % 10:
return 0
# 从队列左侧取出数字（相当于栈的出栈操作）
digit = stack.popleft()
result = result * 10 + digit
# 添加符号
result *= sign
# 最终范围检查
if result < MIN_INT or result > MAX_INT:
return 0
return result
时空复杂度分析
- 时间复杂度：O
(log|x|)- 数字分解和入栈 -
O(log|x|) - 出栈和数字重建 -
O(log|x|)
- 数字分解和入栈 -
- 空间复杂度：
O(log|x|)- 栈空间-
O(log|x|)
- 栈空间-
2.3 最优解法：位运算法
思路
通过逐位提取和重构的方式来反转整数。具体来说：
- 从原数字的最低位开始，一位一位地提取出来
- 将提取出的数字重新组合，构建反转后的数字
示例
输入: x = 123
第一次循环：
- x = 123
- digit = 123 % 10 = 3
- result = 0 * 10 + 3 = 3
- x = 123 / 10 = 12
第二次循环：
- x = 12
- digit = 12 % 10 = 2
- result = 3 * 10 + 2 = 32
- x = 12 / 10 = 1
第三次循环：
- x = 1
- digit = 1 % 10 = 1
- result = 32 * 10 + 1 = 321
- x = 1 / 10 = 0
循环结束，返回321
python代码
class Solution:
def reverse(self, x: int) -> int:
"""
使用位运算方法实现整数反转
参数：
x: 输入的整数
返回：
反转后的整数，如果溢出返回0
"""
# 定义32位整数的范围
MAX_INT = 2**31 - 1 # 2147483647
MIN_INT = -2**31 # -2147483648
# 特殊情况处理
if x == 0:
return 0
# 转换为正数处理，记录符号
sign = 1
if x < 0:
sign = -1
x = -x
result = 0
while x:
# 获取最低位数字
# 使用位运算获取个位数：x & ((1 << 4) - 1) 等价于 x % 10
digit = x % 10
# 溢出检查
if result > MAX_INT // 10 or (result == MAX_INT // 10 and digit > MAX_INT % 10):
return 0
# 数字重构：左移一位（乘10）并添加新位
# 使用位运算：(result << 3) + (result << 1) 等价于 result * 10
result = result * 10 + digit
# 去除已处理的最低位
# 使用位运算：x >> n 等价于 x // (1 << n)
x //= 10
# 添加符号并返回
return sign * result
时空复杂度分析
- 时间复杂度分析
O(log|x|)- 循环次数为
O(log|x|)，每次循环的操作分析：- 取模运算 (x % 10) - O(1)
- 溢出检查 - O(1)
- 乘法和加法运算 - O(1)
- 除法运算 (x //= 10) - O(1)
- 循环次数为
- 空间复杂度分析
O(1)
3 题目总结
题目难度：中等
数据结构：栈
算法应用：位运算