前端算法題解?leetcode50-Pow(x,?n)

更新時(shí)間：2022年09月23日 10:13:32 作者：前端_奔跑的蝸牛

這篇文章主要為大家介紹了前端算法題解?leetcode50-Pow(x,?n)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目

題目地址

實(shí)現(xiàn) pow(x, n) ，即計(jì)算 x 的整數(shù) n 次冪函數(shù)（即，xn ）。

示例 1：

輸入： x = 2.00000, n = 10

輸出： 1024.00000

示例 2：

輸入： x = 2.10000, n = 3

輸出： 9.26100

示例 3：.

輸入： x = 2.00000, n = -2

輸出： 0.25000

解釋?zhuān)?2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0

-231 <= n <= 231-1

-104 <= xn <= 104

解題思路-分情況討論

本題可以分幾種情況討論:\

如果 x = 1，那么無(wú)論 n 的值是多少，結(jié)果都是 1
如果 n = 0，那么無(wú)論 x 的值是多少，結(jié)果都是 1
如果 n = 1，那么無(wú)論 x 的值是多少，結(jié)果都是 x
如果 x = -1，那么如果 n 是偶數(shù)，結(jié)果是 1，否則結(jié)果是 -1
如果 n > 0，則結(jié)果為 1 *= x n 次
如果 n < 0，則結(jié)果為 1 /= x n 次

代碼實(shí)現(xiàn)

var myPow = function(x, n) {
    if(x === 1 || n === 0){
        return 1
    }
    if(x===-1){
        return n % 2 ? -1 : 1
    }
    let res = 1
    if(n>0){
        for(let i = 0;i<n;i++){
            res *= x
        }
        return res
    }
    for(let i = 0;i<-n;i++){
        res /= x
        if(x>0 && res<0.000005){
            return res
        }
    }
    return res
}

解題思路-分治

上面的解題思路雖然能解題，但是因?yàn)橐鎸?shí)的進(jìn)行每一次計(jì)算，所以效率比較低。那如何才能提高效率呢？

這里我們可以采用類(lèi)似二分的方法，將 x 的 n 次方拆分為 x^(n/2) * x^(n/2)，以此來(lái)加速計(jì)算的過(guò)程。每次拆分一半，直到 n = 0。因?yàn)槊看蔚奶幚磉壿嬍窍嗤?，所以可以利用遞歸函數(shù)遞歸調(diào)用自己，而退出條件就是 n = 0。

代碼實(shí)現(xiàn)

var myPow = function(x, n) {
  if(n == 0){
    return 1
  }
  if(n < 0){
    return 1 / myPow(x, -n)
  }
  if(n % 2){
    return x * myPow(x, n - 1)
  }
  return myPow(x * x, n / 2)
}

至此我們就完成了 leetcode-50-Pow(x, n)，更多關(guān)于前端算法 Pow(x, n)題解的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: