[leetcode/lintcode 題解] 算法面試真題詳解：x的n次幂

描述

實作 pow(x, n). (n是一個整數)

不用擔心精度，當答案和标準輸出差絕對值小于1e-3時都算正确

線上評測位址：

領扣題庫官網

樣例1
輸入: x = 9.88023, n = 3
輸出: 964.498           

樣例2
輸入: x = 2.1, n = 3
輸出: 9.261           

樣例3
輸入: x = 1, n = 0
輸出: 1           

注意 n 可能是負數, 需要求一下倒數, 可以在一開始把x轉換成倒數, 也可以到最後再把結果轉換為倒數.

那麼現在我們實作 pow(x, n), n 是正整數的版本:

二分即可: 有xn=xn/2∗xn/2xn=xn/2∗xn/2, 是以可以在 O(logn) 的時間複雜度内實作.

又叫快速幂. 有遞歸實作和循環實作的版本.

還可以參考一下 fast power 中的二進制的做法。

public class Solution {
    /**
     * @param x the base number
     * @param n the power number
     * @return the result
     */
    public double myPow(double x, int n) {
        boolean isNegative = false;
        if (n < 0) {
            x = 1 / x;
            isNegative = true;
            n = -(n + 1);       // Avoid overflow when n == MIN_VALUE
        }

        double ans = 1, tmp = x;

        while (n != 0) {
            if (n % 2 == 1) {
                ans *= tmp;
            }
            tmp *= tmp;
            n /= 2;
        }
        
        if (isNegative) {
            ans *= x;
        }
        return ans;
    }
}           

更多題解參考：

九章官網solution