50. Pow(x, n) - Medium

前往題目

想法

• 嘗試寫了recursion但失敗了，沒有考慮到第二種base case x == 0

思路

1. 遞迴的方式，採用divide的方法，每次都把n/2，這樣直接把當前答案乘以自己就可以了，例如$2^{10}$就會被拆成$2^5和2^5$
2. 遇到奇數n要再多乘一次
3. 遇到負數直接1/結果就可以，無需另外考慮

Code

class Solution {
    public double myPow(double x, int n) {
        long nLong = (long) n;
        // Ignore negative condition
        double res = helper(x, Math.abs(nLong));
        // Consider negative condition
        return (nLong >= 0) ? res : 1 / res;
    }

    private double helper(double x, long n) {
        // Base cases
        if (x == 0) return 0;
        if (n == 0) return 1;

        // Divide for optimisation
        double res = helper(x, n / 2);
        // Due to divide, multiply them will do the work
        res = res * res;
        // Odd n should multiply again
        return (n % 2 == 1) ? x * res : res;
    }
}