題目
實(shí)現(xiàn)?pow(x,?n)?，即計(jì)算 x 的 n 次冪函數(shù)（即，xn）。不得使用庫(kù)函數(shù)，同時(shí)不需要考慮大數(shù)問(wèn)題。
示例 1：
輸入：x = 2.00000, n = 10
輸出：1024.00000
示例 2：
輸入：x = 2.10000, n = 3
輸出：9.26100
示例 3：
輸入：x = 2.00000, n = -2
輸出：0.25000
解釋：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1-
n?是一個(gè)整數(shù) - 要么?
x?不為零，要么?n > 0?。 -104 <= xn <= 104
解題思路
1.題目要求我們實(shí)現(xiàn)?pow(x,?n)?函數(shù)，首先我們來(lái)學(xué)習(xí)一下什么是快速冪。
快速冪算法的本質(zhì)是分治算法。舉個(gè)例子，如果我們要計(jì)算 x^{64}，我們可以按照：
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-635813.html
的順序，從 x?開(kāi)始，每次直接把上一次的結(jié)果進(jìn)行平方，計(jì)算 6?次就可以得到 x^{64}?的值，而不需要對(duì) x 乘 63 次 x。
這個(gè)時(shí)候你可能會(huì)有疑問(wèn)，如果在 pow(x,n) 中 n 不會(huì)恰好等于一次的結(jié)果進(jìn)行平方怎么辦？
當(dāng)然我們還是會(huì)發(fā)現(xiàn)一個(gè)規(guī)律，那就是在將 n 化為二進(jìn)制表達(dá)式后，我們需要相乘的就是在二進(jìn)制中位數(shù)為1的地方，舉個(gè)例子: x^13
將13化為二進(jìn)制表達(dá)式后，我們可以發(fā)現(xiàn)它的1，4，8位為 1 。?
所以x^13就等于：
?
所以在n > 0 時(shí)我們需要判斷二進(jìn)制為 1 的位數(shù)（也就是讓 n?% 2 ），若為 1 （就表示最低位為1）我們就需要乘 x，然后令 n = n/2（將已經(jīng)判斷過(guò)的最后一位去除也就是讓1101變?yōu)?10），讓 x = x * x（就是將x變?yōu)閤^2），然后再進(jìn)行判斷二進(jìn)制的第二位是否為1，直到n = 0；
2.當(dāng)n等于負(fù)數(shù)時(shí)，我們只需要令x = 1 / x 即可，然后令 n = -n；這時(shí)我們要重新設(shè)置一個(gè)long類型的變量y，因?yàn)楫?dāng) n =?-2147483648時(shí)，-n 會(huì)超出 int類型。再上述操作完成后，利用正數(shù)的計(jì)算方法進(jìn)行計(jì)算即可。
代碼實(shí)現(xiàn)
class Solution {
public double myPow(double x, int n) {
double sum = 1;
long y = n;
if(y < 0){
y = -y;
x = 1 / x;
}
while(y > 0){
if(y % 2 != 0){
sum = sum * x;
}
y = y / 2;
x = x * x;
}
return sum;
}
}測(cè)試結(jié)果
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-635813.html
?
到了這里，關(guān)于Leetcode-每日一題【劍指 Offer 16. 數(shù)值的整數(shù)次方】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
