1 題目描述

2 解題思路（leetcode官方解法）

當指數(shù)?n?為負數(shù)時，我們可以計算? 再取倒數(shù)得到結果，因此我們只需要考慮?n?為自然數(shù)的情況。

2.1 快速冪+遞歸

由于每次遞歸都會使得指數(shù)減少一半，因此遞歸的層數(shù)為O(logn)，算法可以在很快的時間內得到結果。

class Solution:def myPow(self, x: float, n: int) -> float:def calc(x,n):if(n==0):return 1.0y=calc(x,n//2)if(n%2==0):return y*yelse:return y*y*xif(n>=0): return(calc(x,n))else:return(1.0/calc(x,-n))

2.2 快速冪+迭代

class Solution:def myPow(self, x: float, n: int) -> float:def calc(x,n):ans = 1.0# 貢獻的初始值為 xx_contribute = x# 在對 N 進行二進制拆分的同時計算答案while n > 0:if n % 2 == 1:# 如果 N 二進制表示的最低位為 1，那么需要計入貢獻ans *= x_contribute# 將貢獻不斷地平方x_contribute *= x_contribute# 舍棄 N 二進制表示的最低位，這樣我們每次只要判斷最低位即可n //= 2return ansif(n>=0): return(calc(x,n))else:return(1.0/calc(x,-n))

?

總結

以上是生活随笔為你收集整理的文巾解题 50. Pow(x, n)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。