LeetCode 50. Pow(x, n) [Medium] [C++] 解題筆記

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

EX:

        Input: 2.00000, 10

        Output: 1024.00000

        Input: 2.00000, -2

        Output: 0.25000
        Explanation: 2-2 = 1/22 = 1/4 = 0.25

想法:

    這題直覺就是利用遞迴來解拉，因為 x 的 n 次方可以想成 x^2 的 n / 2 次方，例如 5^4 = (5^2)^2 = 25 ^ 2，

因此我們只需要不斷將 n 除 2 最後就可以只計算某數平方即可(例如上述例子 5^4 等於計算 25^2)，

但必須另外考慮的是 n 若是奇數的話就必須先就 n 變為偶數在進行遞迴，例如 5^5 = 5^4 * 5 = (5^2)^2 * 5 = 25 ^ 2 * 5。

完整程式碼:

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) { return 1; }
        if (n == 1) { return x; }
        if (n == -1) { return 1.0 / x; }
        if (x == 1) { return 1; }
        if (x == -1) { return (n % 2)? -1 : 1; }
        if (n % 2 == 0) { return myPow(x*x, n / 2); }
        if (n % 2) { return (n > 0)? myPow(x, n - 1) * x : myPow(x, n + 1) * 1.0 / x; }
        return 0.0;
    }
};