整数反转

难度:简单

描述

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1

输入:123

输出:321

示例 2

输入:-123

输出:-321

示例 3

输入:120

输出:21

注意

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−2^{31}, 2^{31} − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

题解

思路

通过对 10 整除求余按位依次反转得到最终的结果。

算法

  1. 判断正负得到符号 sign 和剥离符号的单正数 x,进入步骤 2
  2. 对 10 整除求余得到 x 的个位 pop,整除结果作为新的 x,结果 rev 乘以 10 加上得到的 pop 作为新的结果 rev,这个过程类似于弹栈、压栈的过程,类似于下面代码。然后进入步骤 3

    //pop operation:
    pop = x % 10;
    x /= 10;
    
    //push operation:
    temp = rev * 10 + pop;
    rev = temp;
    

    检查溢出

    temp = rev \cdot 10 + pop 可能会出现溢出现象,所以可以提前检查是否会溢出,下面分析一下条件:

    如果 temp = rev \cdot 10 + pop 溢出,那么一定有 rev \ge \frac{INT\_MAX}{10}:

    • 如果 rev > \frac{INT\_MAX}{10}temp = rev \cdot 10 + pop 一定会溢出
    • 如果 rev = \frac{INT\_MAX}{10},只要 pop > 7 那么 temp = rev \cdot 10 + pop 一定会溢出

    所以,在计算 temp = rev \cdot 10 + pop 之前检查一下是否满足以上两个条件其中之一,如果是,直接返回结果 0 即可。

  3. 如果 x 不是 0 重复步骤 2,否则为结果 rev 添加第 1 步得到的符号即 rev * sign,返回最终结果

实现

class Solution {
    func reverse(_ x: Int) -> Int {
        var v = x
        var sign = 1
        if x < 0 {
            sign = -1
            v = -x
        }
        var rev = 0;
        let compared = 2147483648 / 10
        while (v != 0) {
            var pop = 0
            (v, pop) = v.quotientAndRemainder(dividingBy: 10)
            if (rev > compared || (rev == compared && pop > 7))
            {
                return 0
            }
            rev = rev * 10 + pop;
        }
        return rev * sign;
    }
}
class Solution:
    def reverse(self, x: int) -> int:
        sign = 1
        if x < 0:
            sign = -1
            x = -x
        rev = 0
        COMPARED = 2147483648 / 10
        while x != 0:
            pop = x % 10
            x = x // 10
            if rev > COMPARED or (rev == COMPARED and pop > 7):
                return 0
            rev = rev * 10 + pop
        return rev * sign

复杂度分析

  • 时间复杂度:O(\log(x))

    x 中约有 \log_{10}(x) 位数字。

  • 空间复杂度:O(1)

番外

也有一种比较浪的方法,字符串反转法。思路很简单:整数绝对值转换为字符串,然后反转字符串,之后转整数,最后判断溢出,若溢出返回 0,不溢出加符号返回结果。

实现

class Solution {
    func reverse(_ x: Int) -> Int {
        var sign = 1
        var v = x
        if x < 0 {
            sign = -1
            v = -x
        }
        let newStr = String("\(v)".reversed())
        if let num = Int(newStr) {
            if num > 2147483648 {
                return 0
            }
            return num * sign
        }
        return 0
    }
}
class Solution:
    def reverse(self, x: int) -> int:
        sign = 1
        if x < 0:
            sign = -1
            x = -x
        rev = int(str(x)[::-1])
        if rev > 2147483648: return 0
        return sign * rev