LeetCode小白菜笔记[2]：Reverse Integer

7. Reverse Integer [Easy]

题目：

Given a 32-bit signed integer, reverse digits of an integer.
Example 1:

Input: 123
Output:  321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

题目要求为给一个32bit的signed int，将它按十进制位翻转。并且当翻转后的高位有0的时候不显示0。而且当溢出时返回0。

基本思路如下，两个任务：

按位翻转
判断溢出

先做按位翻转，首先，要由低到高逐个取出每一位上的数值；然后，将取出的值由高到低排列起来。取每一位的数值的方法就是先除若干次10，将要取的位置放到最低位，然后模10将数字取出来。

判断溢出的方法：由于我们的返回值是从高位到低位排起来的，可以看作每次将已有的值左移一位，并在末尾加上新取出的值。左移即乘以10，加上末尾的值后可能溢出。由于overflow实际上丢失了信息，即不可逆，所以每做完一次后。都减去末尾的值并除以10，判断是否与之前的一致，如果不一致，则溢出，否则说明没有溢出。

为了说明溢出问题，用C代码实现。因为python如果原来的类型溢出的话会自适应的调整，比如：

a = np.uint8(255)
a = a*10
a
Out[138]: 2550
type(a)
Out[139]: numpy.int64

C代码实现如下：

int reverse(int x) {
    int reversed = 0;
    int newreversed;
    int tail;
    while(x!= 0){
        tail = x % 10;
        newreversed = reversed * 10 + tail;
        if((newreversed - tail)/10 != reversed){
            return 0; // overflow occurs
        }
        reversed = newreversed;
        x = x / 10;        
    }
    return reversed;
}

结果：

这里写图片描述

再用Python实现，这时候判断溢出采用直接与32bit的有符号数的取值范围比较决定。代码和结果如下：

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        MAX_INT = 2 ** 31 - 1
        rev = 0
        sign = int(x > 0) * 2 - 1
        x = sign * x  # make x positive 
        while (not x == 0):
            tail = x % 10
            rev = rev * 10 + tail
            x = x // 10
        return rev * sign * int(rev < MAX_INT)

勉强通过的样子。。。

这里写图片描述

python对于负数的模运算%和整除运算和C不一样啊…这是python的结果：

x = -321
x // 10
Out[170]: -33
x % 10
Out[178]: 9

所以还要转成正数才能进行按位取值，而C不一样：除运算符号相同为正，相异为负，模运算的正负和被除数一样。比如：
-3/16=0， 16/-3=-5， -3%16=-3， 16%-3=1

对于被除数时负数的情况，C的余数为负，而Python的余数始终是正的，而整除又是通过减去余数算的，因此出现了偏差。

总结

不同语言对有些运算处理不一样，需要注意。
习惯了Python和Matlab等，用C的时候常常忘记先定义后使用，还忘记分号….这是不吼滴。

THE END

星期六, 09. 十二月 2017 11:16下午