文章目录
7. 整数反转
题目描述
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−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
解题思路
这道题要求将整数的数字部分反转，同时需要处理溢出问题。这是一个数学运算和边界处理的经典问题。
算法分析
这道题的核心思想是逐位提取并重组，主要解法包括：
- 数学方法：使用取模和除法逐位提取数字
- 字符串方法：转换为字符串后反转
- 位运算优化：使用位运算优化溢出检查
- 溢出处理：在计算过程中检查32位整数范围
问题本质分析
数学方法详解
溢出检查策略
反转过程可视化
负数处理策略
各种解法对比
算法流程图
边界情况处理
时间复杂度分析
graph TD
A[时间复杂度分析] --> B[数字位数]
B --> C[循环次数]
C --> D[每次操作]
B --> E[log₁₀(n)]
C --> F[O_log_n]
D --> G[O_1]
E --> H[n是整数值]
F --> I[总时间复杂度]
G --> I
I --> J[O_log_n]
J --> K[最优解法]
空间复杂度分析
关键优化点
实际应用场景
测试用例设计
代码实现要点
溢出检查时机：
- 在
result * 10之前检查 - 避免实际溢出后再检查
- 在
符号处理：
- 先转为正数处理
- 最后恢复符号
循环终止条件：
- 使用
x != 0而不是x > 0 - 统一处理正负数
- 使用
边界值处理：
- 特殊处理最大/最小32位整数
- 处理反转后溢出的情况
性能优化：
- 使用位运算优化溢出检查
- 减少不必要的条件判断
这个问题的关键在于掌握数字位提取技巧和正确处理溢出情况，通过数学运算实现整数的位序反转，同时确保结果在32位整数范围内。
完整题解代码
package main
import (
"fmt"
"math"
"strconv"
)
// reverse 整数反转 - 数学方法
// 时间复杂度: O(log n)，其中n是整数的位数
// 空间复杂度: O(1)
func reverse(x int) int {
var result int
// 处理负数，先转为正数处理
isNegative := x < 0
if isNegative {
x = -x
}
// 逐位提取并反转
for x > 0 {
digit := x % 10
x /= 10
// 检查溢出：在乘以10之前检查
if result > math.MaxInt32/10 || (result == math.MaxInt32/10 && digit > 7) {
return 0
}
if result < math.MinInt32/10 || (result == math.MinInt32/10 && digit < -8) {
return 0
}
result = result*10 + digit
}
// 恢复符号
if isNegative {
result = -result
}
return result
}
// reverseOptimized 优化版本 - 使用更简洁的逻辑
// 时间复杂度: O(log n)
// 空间复杂度: O(1)
func reverseOptimized(x int) int {
var result int
for x != 0 {
digit := x % 10
x /= 10
// 检查溢出
if result > math.MaxInt32/10 || (result == math.MaxInt32/10 && digit > 7) {
return 0
}
if result < math.MinInt32/10 || (result == math.MinInt32/10 && digit < -8) {
return 0
}
result = result*10 + digit
}
return result
}
// reverseString 字符串方法 - 转换为字符串后反转
// 时间复杂度: O(log n)
// 空间复杂度: O(log n)
func reverseString(x int) int {
// 处理特殊情况
if x == 0 {
return 0
}
// 转换为字符串
str := strconv.Itoa(x)
isNegative := str[0] == '-'
// 如果是负数，去掉负号
if isNegative {
str = str[1:]
}
// 反转字符串
bytes := []byte(str)
for i, j := 0, len(bytes)-1; i < j; i, j = i+1, j-1 {
bytes[i], bytes[j] = bytes[j], bytes[i]
}
// 转换回整数
result, err := strconv.Atoi(string(bytes))
if err != nil {
return 0
}
// 检查溢出
if result > math.MaxInt32 || result < math.MinInt32 {
return 0
}
// 恢复符号
if isNegative {
result = -result
}
return result
}
// reverseBitwise 位运算方法 - 使用位运算优化
// 时间复杂度: O(log n)
// 空间复杂度: O(1)
func reverseBitwise(x int) int {
var result int
for x != 0 {
digit := x % 10
x /= 10
// 使用位运算检查溢出
if result > (math.MaxInt32-digit)/10 {
return 0
}
result = result*10 + digit
}
return result
}
func main() {
// 测试用例1
x1 := 123
result1 := reverse(x1)
fmt.Printf("示例1: x = %d\n", x1)
fmt.Printf("输出: %d\n", result1)
fmt.Printf("期望: 321\n")
fmt.Printf("结果: %t\n", result1 == 321)
fmt.Println()
// 测试用例2
x2 := -123
result2 := reverse(x2)
fmt.Printf("示例2: x = %d\n", x2)
fmt.Printf("输出: %d\n", result2)
fmt.Printf("期望: -321\n")
fmt.Printf("结果: %t\n", result2 == -321)
fmt.Println()
// 测试用例3
x3 := 120
result3 := reverse(x3)
fmt.Printf("示例3: x = %d\n", x3)
fmt.Printf("输出: %d\n", result3)
fmt.Printf("期望: 21\n")
fmt.Printf("结果: %t\n", result3 == 21)
fmt.Println()
// 测试用例4
x4 := 0
result4 := reverse(x4)
fmt.Printf("示例4: x = %d\n", x4)
fmt.Printf("输出: %d\n", result4)
fmt.Printf("期望: 0\n")
fmt.Printf("结果: %t\n", result4 == 0)
fmt.Println()
// 额外测试用例 - 溢出情况
x5 := 1534236469
result5 := reverse(x5)
fmt.Printf("溢出测试: x = %d\n", x5)
fmt.Printf("输出: %d\n", result5)
fmt.Printf("期望: 0 (溢出)\n")
fmt.Printf("结果: %t\n", result5 == 0)
fmt.Println()
// 测试优化版本
fmt.Println("=== 优化版本测试 ===")
result1Opt := reverseOptimized(x1)
result2Opt := reverseOptimized(x2)
fmt.Printf("优化版本示例1: %d\n", result1Opt)
fmt.Printf("优化版本示例2: %d\n", result2Opt)
fmt.Printf("结果一致: %t\n", result1Opt == result1 && result2Opt == result2)
fmt.Println()
// 测试字符串版本
fmt.Println("=== 字符串版本测试 ===")
result1Str := reverseString(x1)
result2Str := reverseString(x2)
fmt.Printf("字符串版本示例1: %d\n", result1Str)
fmt.Printf("字符串版本示例2: %d\n", result2Str)
fmt.Printf("结果一致: %t\n", result1Str == result1 && result2Str == result2)
fmt.Println()
// 测试位运算版本
fmt.Println("=== 位运算版本测试 ===")
result1Bit := reverseBitwise(x1)
result2Bit := reverseBitwise(x2)
fmt.Printf("位运算版本示例1: %d\n", result1Bit)
fmt.Printf("位运算版本示例2: %d\n", result2Bit)
fmt.Printf("结果一致: %t\n", result1Bit == result1 && result2Bit == result2)
fmt.Println()
// 边界值测试
fmt.Println("=== 边界值测试 ===")
boundaryTests := []int{
math.MaxInt32, // 最大32位整数
math.MinInt32, // 最小32位整数
1000000000, // 10位数
-1000000000, // 负数10位数
}
for _, test := range boundaryTests {
result := reverse(test)
fmt.Printf("x = %d, reverse = %d\n", test, result)
}
}