LeetCode #29 #50 2018-08-05

29. Divide Two Integers

https://leetcode.com/problems/divide-two-integers/description/

对于整数处理问题，比较重要的注意点在于符号和处理越界的问题。而python 自带大数整数运算，整数不会溢出，只要内存足够，所以我们只用考虑符号问题即可，非常方便。我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2⁰+a_1*2¹+a_2*2²+...+a_n*2ⁿ。基于以上这个公式以及左移一位相当于乘以2，我们让除数不断左移直到大于被除数，然后接下来我们每次尝试减去这个基，如果可以则结果增加2^k。因为这个方法的迭代次数是按2的幂直到超过结果，所以时间复杂度为O(logn)。
代码如下：

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        isPos = (dividend < 0) is (divisor < 0)
        devidend, divisor = abs(dividend), abs(divisor)
        res = 0
        while devidend >= divisor:
            temp, i = divisor, 1
            while devidend >= temp:
                res += i
                devidend -= temp
                temp <<= 1
                i <<= 1
        if not isPos:
            res = -res
        return min(max(-(1<<31), res), (1<<31) - 1)
        # return min(max(-2147483648, res), 2147483647)

50. Pow(x, n)

https://leetcode.com/problems/powx-n/description/

一般来说数值计算的题目可以用两种方法来解，一种是以2为基进行位处理的方法，另一种是用二分法。这道题这两种方法都可以解。

第一种方法在Divide Two Integers使用过，就是把n看成是以2为基的位构成的，因此每一位是对应x的一个幂数，然后迭代直到n到最高位。比如说第一位对应x，第二位对应x*x,第三位对应x⁴,...,第k位对应x⁽²^^(k-1)),可以看出后面一位对应的数等于前面一位对应数的平方，所以可以进行迭代。因为迭代次数等于n的位数，所以算法的时间复杂度是O(logn)。
代码如下：

class Solution:
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0:
            x = 1 / x
            n = -n
        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

二分法的解法，如同我们在Sqrt(x)的方法。不过这道题用递归来解比较容易理解，把x的n次方划分成两个x的n/2次方相乘，然后递归求解子问题，结束条件是n为0返回1。因为是对n进行二分，时间复杂度和上面方法一样，也是O(logn)。
代码如下：

class Solution:
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if not n:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2:
            return x * self.myPow(x, n - 1)
        return self.myPow(x * x, n / 2)