前言
該系列文章為本人刷leetcode的記錄,主要旨在分享刷題的思路及演算法決議(盡可能的一題多解),另方便自己日后查閱回顧，代碼的實作語言是python和go，
想進大廠免不了刷題,一起加油吧，小伙伴們！
題目
offer 第16題 數值的整數次方(medium)
鏈接: https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
題目內容
實作pow(x,n),即計算x的n次冪(x^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
-104 <= xn <= 104
解題思路
實作pow(x,n),即計算x的n次冪(x^n)，不得使用庫函式,同時不需要考慮大數問題
分析:計算x的n次冪;
解法1:遞回法
解法2:非遞回法:快速冪法
代碼實作
python
class Solution:
def myPow(self, x: float, n: int) -> float:
#方法1:尾遞回;該題很明顯是階乘相類似的問題;就是不斷重復乘以x
#尾遞回也會超時
flag=0
if n<0: n=-n;flag=1
def recur_tail(n,sum):
#迭代終止條件
if n==0:
if flag==1: return 1/sum
return sum
else:
return recur_tail(n-1,sum*x)
return recur_tail(n,1)
# 粗暴解法;直接回圈
# sum =1
# for i in range(n):
# sum *=x
#return sum
#方法2：快速冪
#針對比如a^b 假如是3^11=3^(2^0+2^1+2^3)=(3^1)*(3^2)*(3^8);
#所以將原來算11次的現在縮短到計算三次即可;
#那么怎么計算這三項呢;實際上,上式的1,2,8都是表示b的二進制表示的第1,2,8位上為1;
#由15題可知對于b的二進制表示時有多少個1的求法我們已經知道了;
#那么本題就是每當b的二進制中第x位有1出現時就將a^x進行累乘就行;x位為0時不用累乘;(就是將原來的count++替換成a^x的累乘)
#
# flag=0
# if n<0:n=-n; flag=1
# ret =1
# a=x
# while n>0:
# if n&1:#如果第x位為1則需要納入累乘
# ret *= a
# a *=a
# n >>=1
# if flag==1: ret=1/ret
# return ret
go
//整數的n次冪
func POW(x, n int) int{
//方法1:尾遞回
//尾遞回也會超時
flag := 0
if n<0{n=-n;flag=1}
var recur_tail func(n int,sum float64) float64
recur_tail = func(n int,sum float64) float64 {
//遞回終止條件
if n == 0 {
if flag==1{return 1/sum}
return sum
}else{
return recur_tail(n-1,sum*x)
}
}
return recur_tail(n,float64(1))
//寫一下遞回
//遞回終止條件
//if n==0{return 1
//}else{
// return x*POW(x,n-1)
//}
//方法2:快速冪方法
flag := 0
if n<0{n=-n;flag=1}
ret := float64(1)
for n>0{
if n&1==1{
ret *= x
}
x *=x
n >>=1
}
if flag==1{ret = 1/ret}
}
總結
注意快速冪的解法套路;需要熟練掌握; 注意這里需要考慮n<0的情況;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352132.html
標籤：其他