leetcode题解50：Pow(x, n)

描述

该题来自于力扣第50题

分析

一个非常简单的思路就是递归，当n是偶数时，计算pow(x,n/2)*pow(x,n/2)，则n是奇数时，计算x * pow(x,(n-1)/2) * pow(x, (n-1)/2)，一直递归直到n为1。

这里介绍另一种方法，使用迭代。考虑$x^n$时，将$n$表示成二进制$a_k \times 2^k + a_{k-1} \times 2^(k-1) + \cdots + a_0 \times 2^0$，从而

又因为$x^{2^k} = (x^{2^{k-1}})^2$，所以只需要依次计算$x^{2^i}$，当第$i$为二进制位$a_i=1$时，将$x^{2^i}$计入结果就好。

那$x^{10}$为例，$10$的二进制为$1010$，计算每个$x^{2^i}$，就是$x^8 \quad x^4 \quad x^2 \quad x$，二进制位为1的有$2^8 \quad 2^2$，所以$x^{10} = x^8 \times x^2$。

算法

1. 初始化结果为ans = 1，循环直到n == 0;
2. 判断n的末尾是不是1，如果是1，则执行第3步；
3. 记录结果，ans *= x
4. 更新x，x *= x
5. 将n右移一位

上述算法只考虑n>=0的情况，若n<0，则计算1 / pow(x, -n)即可

代码

def myPow(self, x: float, n: int) -> float:
    if n < 0:
        return 1 / self.mypow(x, -n)
    return self.mypow(x, n)