简介

吃完午饭，在午休的时间然后玩下lc。已经好久不写博客了，挑个easy的题目玩玩，然后水下。 7. 整数反转

描述

给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。  

示例 1：

输入：x = 123 输出：321

链接：https://leetcode-cn.com/problems/reverse-integer

思路

取最后一位

反转的话，如果能把每一个取出来就很简单了。

比如, 1234，取4的话，只要 1234 % 10

比如, 123， 取3的话，只要 123 % 10

ok，取最后一位可以直接用%10。

如果是中间的直接只要把用过的最后一位踢掉，就可以了。这里使用/10踢掉用过的位。

lc给出的函数原型是

1
2

func reverse(x int) int {
}

看到原型真是乐开花。如果不考虑 假设环境不允许存储 64 位整数（有符号或无符号）。。简直就是关爱。 go里面的int是64 bit。如果考虑32位溢出，直接拿rv和math.MaxInt32比较就行，直接先取每一位，再拼出来。

拼接

1

12 = 1 * 10 + 2

123 = 12 * 10 + 3

简单归纳下。直接得到 rv = rv * 10 + curr

直接输出

 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 {

	sign := 1
	if x < 0 {
		x = -x
		sign = -1
	}

	rv := 0
	for x > 0 {

		rv = rv*10 + (x % 10)
        if  rv > math.MaxInt32 {
		    return 0
	    }
		x /= 10
	}

	return sign * rv
}

测试下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func main() {
	type test struct {
		in   int
		need int
	}

	for _, v := range []test{
		{1234, 4321},
		{-1234, -4321},
		{120, 21},
		{math.MinInt64, 0},
		{math.MaxInt64, 0},
	} {

		got := reverse(v.in)
		if got != v.need {
			fmt.Printf("in:%d, got:%d, need:%d\n", v.in, got, v.need)
			break
		}
	}
}

完全扣题意的做法

还是考虑判断溢出的事情，不使用int取巧 INT_MAX 指代32最大正整数

rv * 10 + x 如果这个式子溢出，肯定满足rv * 10 + x > INT_MAX。 先忽略x，看rv * 10的情况， 如果rv * 10 >= INT_MAX

这里为了简单，先考虑正数溢出的情况

  1. 如果rv * 10 > INT_MAX为真，那rv * 10 + x也满足 > INT_MAX。x >= 0都满足条件，忽略x表达式， 变形就是rv > INT_MAX/10

  2. rv * 10 == INT_MAX,
    这里讨论rv的取值范围，和x的取值范围

    先同时/10, 得到

    rv = INT_MAX/10 同时*10

    rv * 10 = INT_MAX/10 + INT_MAX % 10

    rv * 10 = INT_MAX/10 + 7

    INT_MAX = INT_MAX/10 + 7

    根据INT_MAX代入rv * 10就是

    INT_MAX/10 + 7 + x，其中x > 0 就不满足，合并7+x = curr，curr > 7，就可以判断溢出

    最后得到

    1
2
3

    if rv == INT_MAX/10  && curr > 7 {
    return 0
}

  3. rv * 10 < INT_MAX，已经讨论第2种情况rv * 10 == INT_MAX情况，小于的情况没必要讨论

贴下代码

撸下思路，还是可以的。

 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 {
	rv := 0

	for x != 0 {
		curr := x % 10
		x /= 10

		if rv > math.MaxInt32/10 || rv == math.MaxInt32/10 && curr > 7 {
			return 0
		}

		if rv < math.MinInt32/10 || rv == math.MaxInt32/10 && curr < -8 {
			return 0
		}

		rv = rv*10 + curr

	}

	return rv
}

总结

形式推导的过程很好玩，推成功，最优解就20s写完。