實現(xiàn) pow(x, n) ，即計算 x 的整數(shù) n 次冪函數(shù)（即，xn ）。
暴力方法肯定是循環(huán)循環(huán)n次，
每一次*x
顯然此方法遇到大的數(shù)字會超時
那么我們要引進一個思想，快速冪算法
例如： x^97文章來源：http://www.zghlxwxcb.cn/news/detail-642324.html
我們可以看出，從右向左
每當n為奇數(shù)時，就會多乘一次x
例如：x97 = x48 * x48 * x;
當n為偶數(shù)時，不需要此操作
x48 = x24 * x24 ;
由于從0~97 遍歷的話 我們不知道何時+1；
所以我們選擇從97~0遞歸
接下來代碼實現(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-642324.html
double quickly_pow(double x,long long N)
{
if(N==0)
{
return 1.00;
}
else
{
double y=quickly_pow(x,N/2);
return N%2==0?y*y:y*y*x;
}
}
double myPow(double x, int n)
{
long long N=n;
return N>0?quickly_pow(x,N):1.0/quickly_pow(x,-N);
}
到了這里，關(guān)于leetcode經(jīng)典算法——快速冪的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
