进入刷题刷到 leetcode 7: Reverse Integer。一道easy的题目,但是始终做不对,难点在于它对整数溢出的判断。并且还有一些细节是值得品味的。
整数溢出
对于32位的有符号整数,其最大值为 开头0剩余1,最小值为 开头1剩余0,在go语言中分别为: math.MaxInt32 与 math.MinInt32。
在题目的逻辑中,有 ans = ans * 10 + x % 10
的逻辑,那么如何判断溢出呢?
for x != 0 {
// 判断溢出
if(ans < math.MinInt32 / 10 || (ans == math.MinInt32 / 10 && x % 10 < math.MinInt32 % 10)) {
// 溢出
return
}
ans = ans * 10 + x % 10
x /= 10
}
if 语句中干的事情很简单,就是在ans*10之前,判断当前的ans是否小于 最小值/10 (或 大于最大值/10),如果条件成立,则说明 ans 进行 *10 操作之后的结果一定就小于最小值(或大于最大值),那么在 *10 之前就可以判断 ans 会溢出。
其他细节
对于此题,还有一个值得注意的细节在于正数、负数的不同。直觉的做法是,如果是负数,那么先将其变换为正数,操作完后再加上负号。
但这里更加合理的做法是:如果是正数,则转换为负数,操作完后再取绝对值。
这样做的原因是,32-bit有符号的负数所能表示的范围比正数多1。如果转换成正数来做,那么操作过程中如果出现 math.abs(INT_MIN),操作过程会判断溢出,因为正数无法承载math.abs(INT_MIN),但实际上 INT_MIN 是可以存在的,从而导致误判。