Implement pow(x, n).
解題思路
首先給大家介紹一下快速冪算法
以mn為例，可以先將n轉(zhuǎn)換為二進制數(shù)，例如
m11 = m(20+21+23)
再將式子進行一下變形智玻，就可以得到
m11 = m20m21m23
然后我們就可以通過迭代來計算m2i,這樣就可以把算法的復(fù)雜度降到O(nlogn)了
舉個栗子
以211為例罕扎，我們用變量ans存儲結(jié)果国拇，用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: 有人會問這里為什么要多此一舉轉(zhuǎn)換為
long long,是因為我在數(shù)據(jù)里看到了-2147483648诱咏。所以，你懂的~
