LeetCode 7. 整数反转（易）

记录了Python位运算的基本操作

题目

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

注意:

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

示例

示例 1:

1
2
输入: 123
输出: 321

示例 2:

1
2
输入: -123
输出: -321

示例 3:

1
2
输入: 120
输出: 21

考察知识点

数组、位移运算、边界条件

核心思想

针对优化解 可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。反转整数的方法可以与反转字符串进行类比。我们想重复“弹出” x 的最后一位数字，并将它“推入”到 res 的后面。最后，res 将与 x 相反。

Python版本

输入输出都必须要检测是否越界
关键一行

1
res = res*10 + y%10

自己手写的一个版本

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def reverse(self, x: int) -> int:
        if x < -2147483648 or x > 2147483647:
             return 0
        
        if -10 < x < 10:
            return x
        
        _convert = False
        if x < 0:
            x = 0-x
            _convert = True
        
        result = []
        while x != 0:
            remainder = x%10
            result.append(remainder)
            x = x//10

        tmp = 0
        _len = len(result)
        _scale = 1
        for i in range(_len):
            for j in range(_len-i-1):
                _scale = _scale*10
            tmp += _scale * result[i]
            _scale = 1
        
        tmp = 0-tmp if _convert else tmp
		
        # 不仅要在开始设置溢出判断 也要在return的时候进行溢出判断
        return tmp if -2147483648 < tmp < 2147483647 else 0

print("leet code accept!!!")
s = [1534236469, 123, -123, 120]
Answer = [9646324351, 321, -321, 21]


if __name__ == "__main__":
    solution = Solution()
    for i in range(len(s)):
        print("-"*50)
        result = solution.reverse(s[i])
        print(result)
        print(result==Answer[i])
提交结果 执行用时 内存消耗 语言
通过 32 ms 13.1 MB Python3

自己手写的版本

基于将int转成字符串，字符串反转的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def reverse(self, x: int) -> int:
        if x < -2147483648 or x > 2147483647:
             return 0
        
        if -10 < x < 10:
            return x

        _convert = False
        if x < 0:
            x = 0-x
            _convert = True

        str_x = str(x)
        tmp_str = ""
        for i in range(len(str_x)-1, -1, -1):
            tmp_str += str_x[i]
        # str_x = str_x[::-1]  # 这种方法也可以在Python里面实现字符串翻转（reverse）
        x = int(tmp_str)
        x = 0-x if _convert else x

        return x if -2147483648 < x < 2147483647 else 0
提交结果 执行用时 内存消耗 语言
通过 44 ms 13.2 MB Python3

一个更加简洁、高效的优化版本

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverse(self, x: int) -> int:
        # y, res = abs(x), 0  # 能不用API就不要用API
        y, res = x if x>=0 else 0-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  # 根据输入判断输出是否取反
提交结果 执行用时 内存消耗 语言
通过 40 ms 12.9 MB Python3

时间复杂度：\(O(log(x))\)，\(x\)中大约有\(log10(x)\) 位数字。 空间复杂度：\(O(1)\)

有效语法糖

python的位运算符

a 为 60，b 为 13，二进制格式如下：a = 0011 1100; b = 0000 1101。

  • (a & b) 按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0 输出结果 12 ，二进制解释： 0000 1100
  • (a | b) 按位或运算符：只要对应的二个二进位有一个为1时，结果位就为1。 输出结果 61 ，二进制解释： 0011 1101
  • (a ^ b) 按位异或运算符：当两对应的二进位相异时，结果为1 输出结果 49 ，二进制解释： 0011 0001
  • (~a ) 按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1 。~x 类似于 -x-1 输出结果 -61 ，二进制解释： 1100 0011，在一个有符号二进制数的补码形式。
  • a << 2 等价于 \(a \times 2^2\) 左移动运算符：运算数的各二进位全部左移若干位，由 << 右边的数字指定了移动的位数，高位丢弃，低位补0。
1
2
3
4
>> a = 15
>>> b = a << 4
>>> b
240

输出结果 240 ，二进制解释： 1111 (15) 右移四位得到11110000（240）

  • a >> 2 等价于 \(a \div 2^2\) 右移动运算符：把">>"左边的运算数的各二进位全部右移若干位，>> 右边的数字指定了移动的位数 输出结果 15 ，二进制解释： 0000 1111

python赋值运算符

= 乘法赋值运算符 c = a 等效于 c = c * a /= 除法赋值运算符 c /= a 等效于 c = c / a %= 取模赋值运算符 c %= a 等效于 c = c % a **= 幂赋值运算符 c **= a 等效于 c = c ** a //= 取整除赋值运算符 c //= a 等效于 c = c // a