算功@LeetCode:ReverseInteger

Log

• 【170411】完成 01 版提交（Python）
• 【170412】完成 01 版笔记
• 【170416】看完参考答案，并记录思路（似乎我的就可以算最优解了）

题目

Reverse Integer

【题目类型备注】

数学

提交

01

【语言】

Python

【时间】

170411

【思路】

1. 思路是把反转整数的问题，转化成反转字符串的问题
2. 要反转字符串，就必须要处理符号的问题。这个不难，符号可用 math.fabs(x)/x 来判断，最后返回答案前处理一下即可
3. 反转时，要考虑末尾为 0 的情况：例如 120 反转后就成了 21
4. 反转时如何判断是否溢出（上溢出，下溢出）？最开始我想用对数函数 math.log() 来判断，但后来想：如果真的是在仅允许 32 位带符号整数存在的地方，任何溢出的数字输入后，恐怕都会直接溢出，反而使指数变小；但若直接字符串反转，并把边界数（32 位带符号正整数最大值、负整数最小值）变成字符串，最后用字符串来比较，那么就可以避开那种问题了

【代码】

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        import math
        # If fabs(x) less than 10
        if (math.fabs(x) < 10):
          return x
        else:
          xx = math.fabs(x)
          sign_x = int(math.fabs(x)/x)
          answer  = ''
        # 
        if (0 == xx % 10):
          # Dealing with the zeros in the end
          remainder = int(xx % 10)
          while (0 == remainder):
            xx = xx // 10
            remainder = int(xx % 10)
          # Start reversing
          while not (0 == remainder and 0 == xx):
            answer += str(remainder)
            xx = xx // 10
            remainder = int(xx % 10)

        else:
          remainder = xx % 10
          while not (0 == remainder and 0 == xx):
            answer += str(int(remainder))
            xx = xx // 10
            remainder = xx % 10

        maxinteger = int(math.pow(2, 31))-1
        maxintStr = str(maxinteger)
        if len(answer) == len(maxintStr):
            if (1==sign_x and answer>maxintStr) or (-1==sign_x and answer>(maxintStr[:-1]+str(int(maxintStr[-1])+1))):
              answer = '0'

        return int(answer) * sign_x

【结果】

运行时：59 ms

报告链接：https://leetcode.com/submissions/detail/99786771/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 58.30% of python submissions.

少见的几乎一次提交就成功的（其实这是第二次提交，第一次提交时是把「32位带符号整数」理解错了，但总之改得很快，就一个数字）。不过看来或许还有更快的解法，有待之后研究参考答案。

00

参考解法：

参考答案中 C++ 的最优解和 Java 的最优解的思路主要还是利用了系统边界值的特性，而且无法处理负数的情况。

而 Python 的参考解法则近乎炫技式的解法，似乎和算法关系不太大，主要是语言特性相关的技巧吧好像。暂时看不懂…

所以可能我的才是最优解……如果不炫技的话 :-P