整数反转

题目

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-integer

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321
1
2

示例 2:

输入: -123
输出: -321
1
2

示例 3:

输入: 120
输出: 21
1
2

注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

分析

数字反转,使用余数和整除即可完成。此题的难点在于要考虑溢出的问题。而且由于很多语言是很容易支持长整型,甚至将 int32、int64 在使用上不进行区分,因此需要想办法判断 32 位下如何溢出的。

Go 语言实现

思路:每个数字依次获取,进位累加即可。需要注意累加前的溢出判断。溢出通常不会造成错误,仅仅会使用溢出值来表示,所以需要自己额外判定。

以下编码在 LeetCode 上的表现如下:

执行用时 :0 ms, 在所有 golang 提交中击败了100.00%的用户

内存消耗 :2.2 MB, 在所有 golang 提交中击败了90.87%的用户

func reverseInteger(x int) int {
	x32 := int32(x)
	// 固定边界
	var max32, min32 int32 = 2147483647, -2147483648
	// 结果
	var r32 int32 = 0
	// 只要持续除10未除尽,保持循环
	for ;x32!=0; x32 /= 10{
		// 判断累加前是否越界
		// 由于 int32 首位只能是 1 或 2 ,因此不需要做位数为 >7 或 >8 的判断
		//if r32 > max32/10 || (r32 == max32/10 && x32%10 > 7) {
		if r32 > max32/10 {
			return 0
		}
		//if r32 < min32/10 || (r32 == min32/10 && x32%10 > 8) {
		if r32 < min32/10 {
			return 0
		}
		// 累加
		r32 = r32*10 + x32 % 10
	}
	// 返回结果
	return int(r32)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

编码中全部使用了 int32 保证数据的整体性。

若可以使用长整型,则使用下面的方法也可以实现,更简单:

// int64 的例子
// 使用了 int64,有点跑题,题目限制在 32bit integer中
func reverseInteger1(x int) int {
	// 固定边界
	max, min :=2147483647, -2147483648
	// 结果
	r := 0
	// 只要持续除10未除尽,保持循环
	for ;x!=0; x /= 10{
		// 累加
		r = r*10 + x % 10
	}
	// 判定越界
	if r < min || r > max {
		return 0
	}
	return r
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

此编码不会出现溢出的问题,仅仅是判断大小值即可!