[LeetCode] Reverse_Integer_20190114
题目
leetcode
难度等级: easy
Given a 32-bit
signed integer, reverse digits of an integer.
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit
signed integer range: [−2**31, 2**31 − 1]
. For the purpose of this problem, assume that your function returns 0
when the reversed integer overflows.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
思路
方法1: 直接把数字转换成字符串,之后利用字符串切片或者是列表直接翻转即可。
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
if x.bit_length() >= 32:
return 0
is_negative = True if x<0 else False
str_res = ""
str_x = str(abs(x))
length = len(str_x)
for i in range(length):
str_res += str_x[-1:] # 取最后一位置于第一位
str_x = str_x[:-1] # 去掉最后一位
if is_negative: # 小于0则加上负号
str_res = "-" + str_res
res = int(str_res)
if res.bit_length() >= 32:
return 0
return res
方法2: 利用数学方法,首先获取获得该书十进制位数,再利用模运算及整除方法,依次获取每一位数值,能得到每一位数字就能计算得到翻转的结果。
class Solution:
def get_len(self, num):
"""Get the number length by mathematical calculation"""
length = 0 # 用于计算数字长度
if num < 0: # 考虑负数的情况
num = -(num) # or abs()
while True:
num = num // 10
length += 1
if num == 0:
break
return length
def reverse_num(self, num, length):
"""Flip Numbers through math"""
is_negative = True if num < 0 else False # 负数的情况,添加标志位
res = 0
num = abs(num)
pow_num = length-1 # 10的次方数,用于计算翻转数结果
if num.bit_length() >= 32: # 原始数据溢出
return 0
while True:
temp = divmod(num, 10)
res += temp[1] * 10**pow_num
pow_num -= 1
num = temp[0]
if num == 0:
break
if res.bit_length() >= 32: # 翻转后结果溢出
return 0
if is_negative:
res = -(res)
return res
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
length = self.get_len(x)
res = self.reverse_num(x, length)
return res
结果
上图截图是字符串操作的运行结果,数学计算方法也在84到92之间,不过这个结果在排行中都是比较慢的方法了,快的基本在60ms以下。
分析总结
这道题真的很简单,和我的第一想法一样,但是不幸的是审题错误让我很快放弃了第一想法,并且耗费了以小时为单位的很多时间。
我看到题目的第一瞬间想到的便是字符串翻转或者数组翻转直接完事(最终确实可以如此),写了简单的代码,翻转很成功,但是提交不通过(第一次审题错误,忽略了空间要求),我重新去看题目,发现是对空间有要求的,但是遗憾的是我的理解完全偏差了(第二次审题错误),事实上题目只对输入输出数据的占用空间有要求,而我却理解成了在整个代码运行中,任何一处空间都只能低于32bit
,所有我摒弃了字符串和列表的方法,尝试使用位运算,不过由于技术达不到,尝试良久后放弃,最后我选择了数学计算。
代码算顺利完成,遗憾的是,提交过程中总共1032
个test
,我止步于1027
,依然提示溢出,我反复测试,提供给我的数据是1534236469
,本身只有31
位,但是翻转后居然有34
位,我开始纳闷了,这样结果无论如何也不可能正确啊!于是我开始了第三次审题,这次终于发现了,题目要求溢出只需要返回0
即可,这是多么让人震惊!
如此简单的一道题,就因为我一而再再而三的马虎,不断地被复杂化,而最终的解决方案也不过是在之前的代码中加上两个if
判断。所以这道题目于我本身的意义不仅仅是记录思路和解法,更重要的是对自己态度问题一次反馈,也希望能给大家一个提示,认真审题,认真做事,南辕北辙再努力也没用。
当然,代码本身也不算优美,仅仅是解决了问题,这里有更加优美而简洁的代码供大家参考。 leetcode解答