reverse-integer#7

发表于 更新于 分类于 本文字数： 360 阅读时长 ≈ 1 分钟

问题

整数反转#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的后面。最后，result与num相反。

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

数学方法

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
}

参考