leetcode - 0007 整数反转

https://leetcode-cn.com/problems/reverse-integer/

解法一

俗话说，大力出奇迹。第一个解法，必须是暴力法。

class Solution:
    def reverse(self, x: int) -> int:
        if x < 0:
            sign = -1
        else:
            sign = 1
        x *= sign
        s = str(x)
        l = list(s)
        l.reverse()
        s1 = ''.join(l)
        res = int(s1) * sign
        if res < -int(0x80000000) or res > 0x7fffffff:
            res = 0
        return res

效率自然就是很差了。

解法二

反转的操作，就相当于每次从 x 中取它的最后一位，然后 push 到另一个栈里。

怎么取呢？取模：pop = x % 10

怎么入栈呢？：rev = rev*10 + pop 就是之前的数左移一位（乘以10），然后加上 pop

class Solution:
    def reverse(self, x: int) -> int:
        sub_intmax = int(0x7fffffff / 10)
        sub_intmin = int(0x80000000 / 10)
        rev = 0
        if x < 0:
            sign = -1
            x = -x
        else:
            sign = 1
        while x != 0:
            pop = x % 10
            if sign > 0 and (rev > sub_intmax or (rev == sub_intmax and pop > 7)):
                return 0
            elif sign < 0 and (rev > sub_intmin or (rev > sub_intmin and pop > 8)):
                return 0
            rev = rev * 10 + pop
            x //= 10
        return rev * sign

结果速度还可以：

注意上边写的比 C 要麻烦很多。因为有一个之前我一直没有注意到的问题。

在 c 语言里：

123 % 10 = 3
-123 %10 = -3

但是在 python 里：

123 % 10 = 3
-123 %10 = 7

我试了 lua 里跟 python 的结果一样（我只会这两种解释型语言）。

负数取模的差别，为什么会这样呢？

取模的结果，就是整除之后的余数。所以结果跟整除的行为密切相关。

整除有几种行为：

向上取整，我没见过
向下取整（floor 除法），python 里就是这样。比如 -7 // 3 = -3（-2.333... 向下取整就是 -3）
向零取整（truncate 除法），c 语言里就是这样，比如 7 / 3 = 2; -7 / 3 = 2

对于 python 中，我们套这个公式

a = nq + r  |r| < |a|

q 是 a 除以 n 的商(quotient)，r 是余数(remainder)

那么有：

-7 = 3*-3 + 2

所以取模的结果就是 2

解法三

看了一个比我上边提交更快的答案，发现是解法一的思路。但我用的不对，直接对 str 取反就行了。

class Solution:
    def reverse(self, x: int) -> int:
        if x == 0:
            return 0
        elif x > 0:
            res = int(str(x)[-1::-1])
        elif x < 0:
            res = -int(str(-x)[-1::-1])
        if res < -0x80000000 or res > 0x7fffffff:
            return 0
        else:
            return res

奇怪的是一样的解答，没有人家的快。

其实思想就是，对于 python 来说，并不存在 32 位的限制。直接先算出结果然后判断是否在范围内即可。而用 c 的话，要小心在 32 位环境上，int、long 都是 32 位的，必须关心一下溢出的情况。

meishaoming / blog

leetcode - 0007 整数反转 #72

解法一

解法二

解法三