![cover](https://img-blog.csdnimg.cn/direct/31ce00ed95734a9aae0c14f68c56a1fe.png)
【经典算法】LeetCode 7 整数反转(Java/C/Python3/Golang实现含注释说明,中等)
方式优点缺点时间复杂度空间复杂度字符串易于理解和实现,适用于多种语言使用了额外的字符串,可能增加内存消耗O(n)O(n)数学不使用额外空间,效率较高实现相对复杂,需要处理溢出情况O(n)O(1)
整数反转
- 标签(题目类型):数学
题目描述
给你一个 32 位的有符号整数 x ,返回将 x 中的数字顺序颠倒后的结果。
注意:
- 假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−2^31, 2^31 − 1]。
- 请根据这个范围,判断反转后整数是否溢出。如果反转后整数溢出则返回 0。
思路及实现
方式一:使用字符串
思路
将整数转换为字符串,然后反转字符串,最后再将反转后的字符串转回整数。注意处理溢出情况。
代码实现
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- |
更多推荐
所有评论(0)