Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

<解題>

看到leetcode網站有分享不同的解法

class Solution {
    public double myPow(double x, int n) {
    if(n==0) return 1;
    else if(n%2==0) return myPow(x*x, n/2);
    else if(n%2==1) return x*myPow(x,n-1);
    else{
        return 1/ myPow(x, -n);
    }
    }  
}

Time: O(log n)

Space: O(log n)