Implement pow(x, n).
解题思路
首先给大家介绍一下快速幂算法
以mn为例，可以先将n转换为二进制数，例如
m11 = m(20+21+23)
再将式子进行一下变形，就可以得到
m11 = m20m21m23
然后我们就可以通过迭代来计算m2i,这样就可以把算法的复杂度降到O(nlogn)了
举个栗子
以211为例，我们用变量ans存储结果，用tmp存储22i的值
已知：
211 = 220221223
Step 1:
初始值 ans = 1， tmp = 220 = 2
Step 2:
因为211里包含了220这项,所以ans = ans*tmp = 2, tmp = 221 = tmp * tmp = 4;
Step 3:
因为211里包含了221这项,所以ans = ans*tmp = 8, tmp = 222 = tmp * tmp = 16;
Step 4:
因为211里不包含222这项,所以ans保持不变, tmp = 223 = tmp * tmp = 256;
Step 5：
因为211里包含了223这项,所以ans = ans*tmp = 2048, tmp = 224 = tmp * tmp = 65536;
以上，我们就算出了211的值。mn也是同理~
代码
class Solution {
public:
double myPow(double x, int n) {
double res = 1.0;
double tmp = x;
long long num = (long long)n;
if (n<0){
num = -num; tmp = 1/x;
}
while (num > 0){
if (num%2 == 1){
res = res*tmp;
}
tmp = tmp*tmp;
num = num/2;
}
return res;
}
};
PS: 有人会问这里为什么要多此一举转换为
long long,是因为我在数据里看到了-2147483648。所以，你懂的~
