> 文档中心 > Python每日一练-----整数反转

Python每日一练-----整数反转

☀(day44:P42)

目录

📝题目:

🚩题目分析:

💡解题思路:

🌈代码实现

✏代码注释

🌈代码实现

🌟 解法一:

🌟解法二 :

✏代码注释


📝题目:

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

⭐示例 1:

输入:x = 123

输出:321

⭐示例 2:

输入:x = -123

输出:-321

⭐示例 3:

输入:x = 120

输出:21

⭐示例 4:

输入:x = 0

输出:0

🚩题目分析:

题目的要求很简单就是将数x反转,难点在于题目所说的不允许存储 64 位整数(有符号或无符号),也就是说x反转后的范围不在 [−2^31, 2^31 − 1] ,就返回 0。

什么意思呢?

首先,2^31 - 1 = 2147483647, - 2^31 = 2147483648。不允许存储 64 位整数(有符号或无符号),也就是说x反转后的范围不在 [−2^31, 2^31 − 1] ,就返回 0。如果x = 1234567899,我们将器直接反转后x = 9987654321 明显 > 2147483648,这就不满足题意。因为不允许储存64位整数,那么我们就需要再反转x = 1234567899之前完成之前判断x是否超出[−2^31, 2^31 − 1]范围。

💡解题思路:

首先我们给出x的转换方法。

number = 0

gw = x % 10

x = x // 10

number = number * 10 + gw

重复这一步骤

-----------------------------------------

如x = 123

gw = 123 % 10 = 3

x = x // 10 = 12

number = 0 * 10 + 3 = 3

------

gw = 12 % 10 = 2

x = x // 10 = 1

number = 3 * 10 + 2 = 32

------

gw = 1 % 10 = 1

x = 1 // 10 = 0

number = 32 * 10 + 1 = 321

接下来我们要做的就是再转化的数值超出范围[−2^31, 2^31 − 1]前判出下一步的转换是否超出范围[−2^31, 2^31 − 1]。

我们设x > 0,    max = 2^31 - 1

max = [max / 10] * 10 + (max mod 10)

这里的[n]表示取整, mod为取模运算,定义公式为A Mod B = A - (A div B) * B, (div含义为取整)。

------------------------------------

如 7 mod 4 = 7 % 4 = 3

-7 mod 4 = -7 % 4 = (-7 ) - (-7 div 4) * 4 = (-7) - 2 * 4 = 1 

--------------------------------------

因为max = 2^31 - 1 = 2147483647 

所以max % 10 = 7

max = [max / 10] * 10 + (max mod 10) = [max / 10] * 10 + 7

由number = number * 10 + gw < max

=== >  number * 10 + gw < [max/ 10] * 10 + 7

===>   (number - [max / 10]) * 10 < 7 - gw

讨论该不等式成立的条件:

  • 当 numbe > [max / 10]时,因为gw >= 0,所以等式不成立
  • 当number = [max / 10]时, 当且仅当gw <= 7等式成立
  • 当number < [max / 10]时, 因为gw <= 9, 所以不等式成立

注意到,当number = [max / 10]时,若还能进行下一步转换(下一步转换不会超出范围),那么说明x的位数和max的位数一样,且进行的下一步转换为将原本x的最高位放到末尾。因为max = 2147483647,最高位为2,所以x进行最高位的转换操作时gw < 2.即number = [max / 10]不等式肯定成立。

得到x > 0的判定条件为:number <=  [max / 10]

x < 0的情况类似,读者可自行证明。

综上得到x时否能进行下一步转换的判定条件为[-2^31 / 10] <= number <= [2^31 - 1]

🌈代码实现

def reverse(x):    min, max = -2 ** 31, 2 ** 31 - 1    number = 0    while x != 0: if number  max // 10:     return 0 gw = x % 10 if x  0:     gw -= 10 x = (x - gw) // 10 number = number * 10 + gw    return number

✏代码注释

def reverse(x):    min, max = -2 ** 31, 2 ** 31 - 1    number = 0    while x != 0: # INT_MIN 也是一个负数,不能写成 rev < INT_MIN // 10 if number  max // 10:     return 0 gw = x % 10 """Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果, 因此这里需要进行特殊判断""" if x  0:  # 如x = -123 或 -10     gw -= 10   # -123 % 10 = 7, gw -= 10 ==> 7-10 = -3, -10 % 10 = 0 """同理,Python3 的整数除法在 x 为负数时会向下(更小的负数)取整, 如-123 // 10 = -13,因此不能写成 x //= 10""" x = (x - gw) // 10 number = number * 10 + gw    return number

时间复杂度:O(log∣x∣)。翻转的次数即 x 十进制的位数。空间复杂度:O(1)

这里再补充如果没有不允许存储 64 位整数(有符号或无符号)的解法

🌈代码实现

🌟 解法一:

def reverse(x):    if x >= 0: x = str(x) x = x[::-1] x = int(x) if x <= 2 ** 31 - 1:     return x else:     return 0    elif x = -2 ** 31:     return -x else:     return 0

 一行解法

def reverse(x):    return [1, -1][x < 0] * int(str(abs(x))[::-1]) if ([1, -1][x < 0] * int(str(abs(x))[::-1])).bit_length() < 32 else 0

 y = [1, -1][x<0]表示, x0取1

🌟解法二 :

def reverse(x):    flag = False      if x  0: number = number * 10 + x % 10 x = x // 10    if flag:   number = -number      if -pow(2, 31) <= number <= pow(2, 31) - 1: return number    return 0

✏代码注释

def reverse(x):    if x >= 0: x = str(x)  # 数值转字符串 x = x[::-1]  # 反转字符串 x = int(x)   # 字符串转数值 if x <= 2 ** 31 - 1:  # 判断范围     return x else:     return 0    elif x = -2 ** 31:     return -x else:     return 0
def reverse(x):    flag = False  # x > 0 时标记值flag = False    if x < 0: x = -x  # 将x转为正数 flag = True  # x  0: number = number * 10 + x % 10 x = x // 10    if flag:  # flag为True时执行,这时x为负数 number = -number  # 将number转会负数    if -pow(2, 31) <= number <= pow(2, 31) - 1: return number    return 0

今天就到这,明天见。🚀

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄

Python每日一练-----整数反转 创作打卡挑战赛 Python每日一练-----整数反转 赢取流量/现金/CSDN周边激励大奖彭州一中