LeetCode Pow(x, n)

LeetCode解題之Pow(x, n)

原題

求x的n次冪。

注意點：

例子：

輸入: x = 2, n = -1

輸出: 0.5

輸入: x = 2.1, n = 2

輸出: 4.41

解題思路

最簡答的方法就是把n個x直接做乘法，但這樣要進行(n-1)次運算。現在以2**8(表示2的8次方)作為例子，需要進行7次乘法，但如果當做(2**2)**4->((2**2)**2)**2來計算就只要做3次乘法。即當n為奇數時，直接乘上當前的x，偶數時x變為x的平方，n除以2。這樣就可以較快速的求出結果。當n為負數時要取倒數。

AC源碼

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


if __name__ == "__main__":
    assert Solution().myPow(2, -1) == 0.5
    assert Solution().myPow(2.1, 2) == 4.41