整数反转

Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1 2	Input: 123 Output: 321

Example 2:

1 2	Input: -123 Output: -321

Example 3:

1 2	Input: 120 Output: 21

Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: $[-2^{31},2^{31}-1]$ . For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

题目大意

对于提供的32位有符号整型数字按位反转得到另一组整型。需要注意的两点：

有符号，即会有负数
按位反转后，可能会超出32位整型的范围，导致溢出，这里需要做处理
32位整型取值范围：-2147483648 ~ 2147483647

解题思路

Tag:数学

通过循环将数字 x 按位拆分，在计算新值时判断是否溢出
溢出条件有两个：
- 一个是大于整数最大值 math.MaxInt32
- 一个是小于整数最小值 math.MinInt32
定义计算结果为 rev，下一位为 pop
- 从 rev * 10 + pop > math.MaxInt32这个条件来看
  - 当出现 rev > math.MaxInt32 / 10 且还有 pop 需要添加时，则一定溢出
  - 当出现 ans == math.MaxInt32 / 10 且 pop > 7 时，则一定溢出，7是 2^31 - 1的个位数
- 从 rev * 10 + pop < math.MinInt32 这个条件来看
  - 当出现 rev < math.MinInt32 / 10 且还有 pop 需要添加时，则一定溢出
  - 当出现 rev == math.MinInt32 / 10 且 pop < -8 时，则一定溢出，8 是-2^31的个位数

代码

func reverse(x int) int {
    rev := 0
    for x!=0 {
        pop := x%10
        x /= 10
        if (rev > math.MaxInt32/10 || (rev == math.MaxInt32 / 10 && pop > 7)){
            return 0
        }
        if (rev < math.MinInt32/10 || (rev == math.MinInt32 / 10 && pop < -8)) {
            return 0
        }
        // https://play.golang.org/p/4UilqCA9nQM
      	// rev*10 在32位下会发生溢出, 所以预先判断
        rev = rev * 10 + pop
    }
    return rev
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。