0050.Pow(x, n)
方法一:递归
时间复杂度 $O(\log n)$,空间复杂度 $O(\log n)$。
func myPow(x float64, n int) float64 {
if n == 0 {
return 1.0
} else if n < 0 {
return myPow(1/x, -n)
}
ans := myPow(x, n>>1)
if n&1 == 1 {
return x * ans * ans
}
return ans * ans
}
方法二:快速乘
时间复杂度 $O(\log n)$,空间复杂度 $O(1)$。
func myPow(x float64, n int) float64 {
if n < 0 {
x, n = 1/x, -n
}
ans, c := 1.0, x
for n != 0 {
if n&1 == 1 {
ans *= c
}
c *= c
n >>= 1
}
return ans
}