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

2022-09-26 14:05:20

題目

題目地址

實現 pow(x, n) ，即計算 x 的整數 n 次冪函數（即，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

解釋： 2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0

-231 <= n <= 231-1

-104 <= xn <= 104

解題思路-分情況討論

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

如果 x = 1，那麼無論 n 的值是多少，結果都是 1
如果 n = 0，那麼無論 x 的值是多少，結果都是 1
如果 n = 1，那麼無論 x 的值是多少，結果都是 x
如果 x = -1，那麼如果 n 是偶數，結果是 1，否則結果是 -1
如果 n > 0，則結果為 1 *= x n 次
如果 n < 0，則結果為 1 /= x 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
}

解題思路-分治

上面的解題思路雖然能解題，但是因為要真實的進行每一次計算，所以效率比較低。那如何才能提高效率呢？

這裡我們可以採用類似二分的方法，將 x 的 n 次方拆分為 x^(n/2) * x^(n/2)，以此來加速計算的過程。每次拆分一半，直到 n = 0。因為每次的處理邏輯是相同的，所以可以利用遞迴函數遞迴呼叫自己，而退出條件就是 n = 0。

程式碼實現

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)，更多關於前端演演算法 Pow(x, n)題解的資料請關注it145.com其它相關文章！

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

目錄

題目

解題思路-分情況討論

程式碼實現

解題思路-分治

程式碼實現

熱門文章