整数反转

• 标签(题目类型)：数学

题目描述

给你一个 32 位的有符号整数 x ，返回将 x 中的数字顺序颠倒后的结果。

注意：

• 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。
• 请根据这个范围，判断反转后整数是否溢出。如果反转后整数溢出则返回 0。

原题：LeetCode 7 整数反转

思路及实现

方式一：使用字符串

思路

将整数转换为字符串，然后反转字符串，最后再将反转后的字符串转回整数。注意处理溢出情况。

代码实现

Java版本

public class Solution {
    public int reverse(int x) {
        // 将整数转换为字符串
        String str = String.valueOf(x);
        StringBuilder sb = new StringBuilder(str);
        // 反转字符串
        String reversedStr = sb.reverse().toString();
        
        // 判断反转后的字符串是否以"-"开头，以决定是否为负数
        boolean isNegative = reversedStr.startsWith("-");
        
        // 去除可能的负号，将字符串转换为长整型，并判断是否会溢出
        long reversedLong = Long.parseLong(isNegative ? reversedStr.substring(1) : reversedStr);
        
        // 判断是否溢出
        if (reversedLong > Integer.MAX_VALUE || reversedLong < Integer.MIN_VALUE) {
            return 0;
        }
        
        // 转换回整数
        return (int) reversedLong;
    }
}

说明：
此方法利用了字符串操作的便利性，但需要注意的是，在转换回整数之前需要判断是否会溢出。

C语言版本

#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int reverse(int x) {
    char str[12]; // 假设整数转换为字符串不会超过11位（包括符号位）
    snprintf(str, sizeof(str), "%d", x);
    int length = strlen(str);
    int isNegative = (str[0] == '-');
    int start = isNegative ? 1 : 0;
    long reversedLong = 0;
    
    for (int i = length - 1; i >= start; i--) {
        reversedLong = reversedLong * 10 + (str[i] - '0');
        // 判断是否会溢出
        if (reversedLong > INT_MAX || reversedLong < INT_MIN) {
            return 0;
        }
    }
    
    return (int)(isNegative ? -reversedLong : reversedLong);
}

说明：
C语言版本直接操作字符串，使用snprintf将整数转换为字符串，然后遍历字符串的每一位进行反转。同时，在反转过程中判断是否会溢出。

Python3版本

class Solution:
    def reverse(self, x: int) -> int:
        # 转换为字符串并反转
        reversed_str = str(x)[::-1]
        
        # 判断反转后的字符串是否以"-"开头，以决定是否为负数
        is_negative = reversed_str.startswith('-')
        
        # 去除可能的负号，转换为整数，并判断是否会溢出
        reversed_int = int(reversed_str) if not is_negative else -int(reversed_str[1:])
        
        # 判断是否溢出
        if reversed_int > 2**31 - 1 or reversed_int < -2**31:
            return 0
        
        return reversed_int

说明：
Python版本同样利用了字符串的便利性，并且在转换为整数之前进行了溢出判断。

Golang版本

package main

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

func reverse(x int) int {
	str := strconv.Itoa(x)
	isNegative := str[0] == '-'
	if isNegative {
		str = str[1:]
	}
	reversedStr := reverseString(str)
	if isNegative {
		reversedStr = "-" + reversedStr
	}
	reversed, err := strconv.Atoi(reversedStr
#### Golang版本

```go
package main

import (
	"math"
	"strconv"
	"strings"
)

func reverse(x int) int {
	// 转换为字符串
	str := strconv.Itoa(x)
	// 反转字符串
	reversedStr := reverseString(str)
	
	// 去除可能的负号，转换为整数
	reversed, err := strconv.Atoi(reversedStr)
	if err != nil {
		return 0
	}
	
	// 判断是否溢出
	if reversed > math.MaxInt32 || reversed < math.MinInt32 {
		return 0
	}
	
	return reversed
}

// 反转字符串
func reverseString(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

func main() {
	// 测试代码
	x := 12345
	reversed := reverse(x)
	fmt.Println(reversed) // 输出: 54321
}

说明：
Golang版本也使用了字符串操作来实现反转，同时考虑了溢出的情况。在reverseString函数中，通过遍历字符串的字符数组并交换首尾字符来实现反转。

复杂度分析

对于所有提供的方法，时间复杂度都是O(n)，其中n是输入整数x的位数。这是因为我们需要遍历每一位数字来进行反转。空间复杂度对于Java、Python和Golang的版本是O(n)，因为我们需要一个额外的字符串来存储反转后的数字。对于C语言的版本，空间复杂度是O(1)因为我们直接在原字符串上进行操作，没有使用额外的空间（假设字符串数组str的大小足够大）。

方式二：使用数学运算

思路

不使用字符串，而是通过数学运算来反转整数。我们可以不断取出x的个位数，将其添加到结果中，并将x除以10以去掉个位数。

代码实现

由于篇幅限制，这里只给出Java版本的实现，其他语言的实现类似。

Java版本

public class Solution {
    public int reverse(int x) {
        int reversed = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            
            // 判断是否会溢出
            if (reversed > Integer.MAX_VALUE/10 || (reversed == Integer.MAX_VALUE / 10 && pop > 7)) {
                return 0;
            }
            if (reversed < Integer.MIN_VALUE/10 || (reversed == Integer.MIN_VALUE / 10 && pop < -8)) {
                return 0;
            }
            
            reversed = reversed * 10 + pop;
        }
        return reversed;
    }
}

说明：
该方法通过循环和取模运算来不断取出x的个位数，并构建反转后的整数。在每次添加新的数字之前，都会检查是否会溢出。

复杂度分析

时间复杂度仍然是O(n)，其中n是输入整数x的位数。空间复杂度是O(1)，因为我们只使用了固定数量的变量来存储中间结果。

总结

方式	优点	缺点	时间复杂度	空间复杂度
字符串	易于理解和实现，适用于多种语言	使用了额外的字符串，可能增加内存消耗	O(n)	O(n)
数学	不使用额外空间，效率较高	实现相对复杂，需要处理溢出情况	O(n)	O(1)

相似题目

相似题目	难度	链接
leetcode 73. 矩阵置零	中等	力扣-73
leetcode 9. 回文数	简单	[力扣-9](https://leetcode-cn.com/problems/palindrome-