【LeetCode】0050 Pow（x，n）

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

# -*- coding:utf-8 -*-

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1.0
        n_negative = False
        if n < 0:
            n = -n
            n_negative = True
        flag = 1
        times = 0
        while 2 * flag <= n:
            flag = flag << 1
            times += 1
        # 尝试判断下一个和当前哪一个离n更近
        n_is_nearly = True
        if flag * 2 - n < n - flag:
            n_is_nearly = False
        sum = x
        for i in range(times):
            sum *= sum
        if n_is_nearly:
            for i in range(n - flag):
                sum *= x
        else:
            sum *= sum
            for i in range(2 * flag - n):
                sum /= x
        return sum if n_negative is False else 1.0 / sum
if __name__ == '__main__':
    x = 0.00001
    n = 2147483647
    print(Solution().myPow(x, n))

思路：这道题第一时间想的就是找一个最大的小于n的2的n次方数，就是比如2的10次方，我们先算10以内最小的2的n次方数，是8，这时我们需要计算3次sum*sum即可得到2的8次方，然后再乘2次即可。

但是有一个2147483647次方的数。。那我们只能判断2的n次方和2的n+1次方和平方数哪个离得远。然后根据情况选择乘除。

思考：

def myPow1(self, x, n):
    """
    :type x: float
    :type n: int
    :rtype: float
    """
    i = n
    if i < 0: i = -i
    res = 1
    while i != 0:
        if i % 2 != 0: res *= x
        x *= x
        i = i // 2
    return res if n > 0 else 1 / res

有一个思路类似，但是空间复杂度相对较低的方法，也是类似的对半查找，如果是奇数就乘一下，偶数就折半。