reverse-integer#7

问题

整数反转#7

Int#reverse

Int定义一个私有的扩展方法reverse

1
2
3
4
// Solution7.kt
private fun Int.reverse(): Int {
// 具体实现
}

单元测试

1
2
3
4
5
6
7
8
9
10
// Soulution7.kt
@Test
fun reverse() {
// "123" 反转之后为 "321"
assert(123.reverse() == 321)
// "-123" 反转之后为 "-321"
assert((-123).reverse() == -321)
// "120" 反转之后为 "21"
assert((120).reverse() == 21)
}

解法

反转整数可以与反转字符串进行类比。

我们想重复弹出num的最后一位数字,并将它推入result的后面。最后,resultnum相反。

要在没有辅助堆栈/数组的帮助下弹出推入数字,我们可以使用数学方法。

数学方法

1
2
3
4
5
6
7
// pop
pop = num % 10
num /= 10

// push
temp = result * 10 + pop
result = temp

但是,这种方法很危险,因为当temp = result*10 + pop时会导致溢出。

假设result是正整数:

  • 如果temp = result*10 + pop导致溢出,那么result >= Int.MAX_VALUE/10
  • 如果result > Int.MAX_VALUE/10,那么temp = result * 10 + pop一定会溢出
  • 如果result = Int.MAX_VALUE/10,那么只要pop > 7,temp = result * 10 + pop就会溢出

result为负整数时同理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 整数反转
*/
private fun Int.reverse(): Int {

// 要反转的整数
var value = this

// 结果
var result = 0

while (value != 0) {
// 计算进位,注意 pop 是带符号的
val pop = value % 10
when {
// 7 是 Int.MAX_VALUE 的第2位
(result > Int.MAX_VALUE / 10) || (result == Int.MAX_VALUE / 10 && pop > 7) ->
return 0
// 8 是 Int.MIN_VALUE 的第2位
(result < Int.MIN_VALUE / 10) || (result == Int.MIN_VALUE / 10 && pop < -8) ->
return 0
}
result = result * 10 + pop
value /= 10
}

return result
}

参考