1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func reverse(x int) int {
const (
intMax = 2147483647
intMin = -2147483648
)
result := 0
for x != 0 {
t := x % 10
if result > intMax/10 || (result==intMax/10 && t>intMax%10) { return 0 }
if result < intMin/10 || (result==intMin/10 && t<intMin%10) { return 0 }
result = result*10 + t
x /= 10
}
return result
}

刚开始使用了一开始就计算出最高位权值,进而直接乘上到达目的位的方法。
此种方法首先要事先求出数字位数才能求各位权值,进行一次循环浪费了时间,
求权值过程中又要进行一次循环,增加时间又增加空间,后续也没有太好的方法判断溢出。
类似

1
2
3
4
5
6
7
8
9
10
11
12
numLen := getNumLen(x)
w:=1
for i:=0; i<numLen;i++ {
w*=10
}
r := 0
for x!=0 {
t := x % 10
r += w * t

w /= 10; x /= 10
}

后来看了循环乘10只需要一次循环,还省去了许多过程与变量,又高效又优雅

1
2
3
4
5
6
7
r := 0
for x!=0 {
t := x %10
x /= 10

r = r * 10 + t
}

而后是添加判断溢出的方法,需要使用数学推导。

重点在于r * 10 + t这一句需要提前判断是否会导致溢出。

假设x为正数,则溢出时有10r+t>intMax。
但是我们不能直接这么写if,因为这样判断本身也会溢出,无法正确判断。
将等式同/10,此时便可以安全判断,r+t/10>intMax/10
但是注意又有新的问题,int会取整,导致/10后范围并不正确。

t的范围是0-9的整数,/10后为[0, 1),取整后得0.
intMax/10=214748364+0.7小数部分是原个位数字,取整后丢失小数,得214748364
若r>[intMax/10],就有r>intMax/10+x(x的范围[0,1)),由于x与t范围[0, 1)一致,也有r>intMax/10+t成立,溢出。
若r==[intMax/10],则还需判断t/10和丢失的小数部分0.7的关系,才能判断原式是否成立,也即t和原intMax的个位数字7的关系,若t>7则成立,溢出。

类似的,负数有
若r<[intMin/10],就有r>intMin/10+x(x的范围(-1, 0]),由于x与t范围(-1, 0]一致,也有r>intMax/10+t成立,溢出。
若r==[intMin/10],则还需判断t/10和丢失的小数部分-0.8的关系,才能判断原式是否成立,也即t和原intMax的个位数字-8的关系,若t<-8则成立,溢出。

总结:

  • 重视数学推导,思路不清晰时可使用数学方法。
  • 计算机的类型虽然有上限,但是数学推导的时候没有范围限制。因而,可以使用数学推导方法推导条件,然后通过变形式子,使得各中间值都落入计算机的表示范围内,如此绕过数值范围问题。
  • 处理此类数值的各位数字时,不必一开始就计算出各位的权值而一次性乘上,也可以通过循环叠加*10来达到目的。