题目描述

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

提示：

-231 <= x <= 231 - 1

解题思路

这个题的思路很简单，就是将整数转换为字符串，然后反转字符串，最后再转换为整数。需要注意的是，反转后的整数可能会超过 32 位的有符号整数的范围，所以需要进行判断。如果超过范围，就返回 0。另外如果整数是负数，那么在反转字符串的时候需要将负号放在最前面。最后再将字符串转换为整数即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func reverse(x int) int {
	neg := false
	if x < 0 {
		neg = true
		x = -x
	}

	xstr := fmt.Sprintf("%d", x)
	reversedInt := 0
	for i := len(xstr) - 1; i >= 0; i-- {
		reversedInt = reversedInt*10 + int(xstr[i]-'0')
	}

	if neg {
		reversedInt = -reversedInt
	}
	if reversedInt < -1<<31 || reversedInt > (1<<31)-1 {
		return 0
	}
	return reversedInt
}

当然上面用到了一个字符串转换的函数，下面是一个不使用字符串的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reverse(x int) int {
	reversedInt := 0

	for x != 0 {
		pop := x % 10
		x = x / 10
		reversedInt = reversedInt*10 + pop
		if reversedInt < -1<<31 || reversedInt > (1<<31)-1 {
			return 0
		}
	}

	return reversedInt
}

这两个方式的时间复杂度都是 O(log10(n))，但是第二种方法不使用字符串，所以更优雅一些。

当然其实这里有一个小问题，题目中假设环境不允许存储 64 位整数（有符号或无符号），但是在 Go 语言中，int 类型在 64 位机器上其实是 64 位的，在代码中是使用 int 类型来存储结果，而 32 位的有符号整数的范围是 [-2^31, 2^31 - 1]。
所以当判断 reversedInt < -1<<31 || reversedInt > (1<<31)-1 时，其实 reversedInt 如果只是 32 位整数的话，会有溢出的可能，只有在 64 位机器上才可以保证正常运行。因为当 reversedInt < -1<<31 || reversedInt > (1<<31)-1 条件成立的时候，reversedInt 的值已经是小于 -1<<31 或者大于 1<<31 了。因此如果在 32 位机器上运行的话，可能会出现错误的结果。

可以尝试强制使用 int32 类型来运行代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reverse(x int) int {
	var reversedInt int32 = 0
	var num int32 = int32(x)

	for num != 0 {
		var pop int32 = num % 10
		num = num / 10
		if reversedInt < -1<<31 || reversedInt > (1<<31)-1 {
			return 0
		}
		reversedInt = reversedInt*10 + pop
	}

	return int(reversedInt)
}

func main() {
    fmt.Println(reverse(1534236469))  // 会输出 1056389759，但实际应该是 0
}

为了避免这个问题，可以将 reversedInt 的类型改为 int32，并在 reversedInt 的加上 pop 之前先判断加上之后是否会溢出，如果会溢出就直接返回 0。这样就可以避免这个问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func reverse(x int) int {
	var reversedInt int32 = 0
	var num int32 = int32(x)

	for num != 0 {
		var pop int32 = num % 10
		num = num / 10
        if reversedInt > (1<<31-1)/10 || (reversedInt == (1<<31-1)/10 && pop > 7) {
            return 0
        }
        if reversedInt < -1<<31/10 || (reversedInt == -1<<31/10 && pop < -8) {
            return 0
        }
		reversedInt = reversedInt*10 + pop
	}

	return int(reversedInt)
}