50. Pow(x, n)

https://leetcode.com/problems/powx-n/
快速幂的实现！

分治，有递归和迭代的处理，写起来要熟练！

递归

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        isNeg = n < 0
        n = -n if isNeg else n
        half = self.myPow(x, n // 2)
        res = half * half
        if n % 2 == 1:
            res *= x
        return 1 / res if isNeg else res

迭代

class Solution:
    def myPow(self, x: float, n: int) -> float:
        isNeg = n < 0
        n = -n if isNeg else n
        res = 1.
        while n > 0:
            if n % 2 == 1:
                res *= x
            x *= x
            n //= 2
        return 1. / res if isNeg else res