leetcode-整数翻转

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
}

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

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只需要一次循环，还省去了许多过程与变量，又高效又优雅

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来达到目的。

Donate