LeetCode题目（Python实现）：整数反转

Dear 丶 2023-07-18 04:48 48阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：用整除剥离每一位
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  想法二：利用字符串反转
     *   *  算法实现
         *  执行结果
     *  官方
     *   *  算法实现
         *  执行结果
     *  小结

# 题目 #

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

**示例1** :

输入: 123
    输出: 321

**示例2** :

输入: -123
    输出: -321

**示例3** :

输入: 120
    输出: 21

**注意**:

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

## 想法一：用整除剥离每一位 ##

反转整数，用的方法是剥离每一位上的数字，同时用另一个变量来将每一位重新赋值，说白了就是剥离的相反操作。

具体操作是，将整数对10取余剥离出最低位，将这一位数字累加给新变量，然后整数除以10得到除去剥离一位剩余的位数。之后判断整数是否有剩余位数，没有的话停止循环；有的话继续循环。

需要注意的是：

1.  上面剥离出的位数累加给新变量前，需要将新变量乘10来使之前的位数向前移动一位，从而空出一位给新剥离出的位数
2.  还有就是由于Python整数除法是向下取整的（小数变为更小的整数），正数的话没有问题，但是负数取整就会有问题，例如-1除以10等于-0.1，向下取整得到-1，所以需要对负数的情况稍加处理，这里的用的是用一个flag来标识，正数为1（对结果没有影响），负数为-1，然后对数字取绝对值按正常正数处理，最后返回结果时乘上flag。

### 算法实现 ###

def reverse(self, x: int) -> int:
        s = 0
        flag = 1
        if x < 0:
            flag = -1
            x = -x
        while x != 0:
            s = s * 10 + x % 10
            x = x // 10
        s = s * flag
        return s if 2147483648 > s >= -2147483648 else 0

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 36 ms, 在所有 Python3 提交中击败了74.58%的用户  
**内存消耗** : 13.7 MB, 在所有 Python3 提交中击败了5.08%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(n)，这里 n 是整数的位数。
 *  空间复杂度：O(1)

## 想法二：利用字符串反转 ##

将整数转化为字符串，将字符串反转，再将字符串转化为整数并输出。

### 算法实现 ###

def reverse(self, x: int) -> int:
        bef = "" if x >= 0 else "-"			# 对负数特殊标志
        var = int(bef + str(abs(x))[::-1]) 	# 反转字符串，并转化为整数
        return var if 2147483648 > var >= -2147483648 else 0

### 执行结果 ###

![在这里插入图片描述][20200324125318389.png]

## 官方 ##

### 算法实现 ###

def reverse(self, x: int) -> int:
        y, res = abs(x), 0
        # 则其数值范围为 [−2^31,  2^31 − 1]
        boundry = (1 << 31) - 1 if x > 0 else 1 << 31
        while y != 0:
            res = res * 10 + y % 10
            if res > boundry:
                return 0
            y //= 10
        return res if x > 0 else -res

### 执行结果 ###

![在这里插入图片描述][20200324131609457.png]

## 小结 ##

题目不是很难，主要的思路还是在于想法一，想法二属于另辟蹊径了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230528/b1f98aebfaa8478f9a0e9d6631f78f88.png
[20200324125318389.png]: /images/20230528/e2b5d84b069e4f3ea4bf5873392304c7.png
[20200324131609457.png]: /images/20230528/e650e4154ccb4c36ad1d5edb52849502.png