劍指 Offer 16. 數(shù)值的整數(shù)次方

實現(xiàn)?pow(x,?n)?，即計算 x 的 n 次冪函數(shù)（即，xn）。不得使用庫函數(shù)，同時不需要考慮大數(shù)問題。

雖然但是我還是一開始試試看能不能暴力……

結(jié)果……果然還是超時了【悲

不要停下來啊

大佬題解：二分法

也就是x^4=(x^2)^2，若n為奇數(shù)，先乘一個x，然后對n進行右移的時候自然就去掉了多出來的1。

class?Solution:

????def?myPow(self,?x:?float,?n:?int)?->?float:

????????if?x==0:return?0

????????res=1

????????if?n<0:

????????????x=1/x

????????????n=-n

????????while?n:

????????????if?n&1:res?*=x???#n&1判斷奇數(shù)偶數(shù)

????????????x?*=x

????????????n>>=1??#右移一位等同于//2

????????return?res