LeetCode (Math) Pow(x, n)

Pow(x, n)

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

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

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

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

思路：首先能想到最原始的方法，就是利用求一个数的n次方的公式。代码如下：

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        if (n > 0) {
            for (int i = 0; i < n; i++) {
                res *= x;
            }
        } else if (n < 0) {
            for (int i = 0; i < -n; i++) {
                res *= x;
            }
            res = 1 / res;
        } 
        return res;
    }
}

该方法虽然正确，但是运行超时。

在网上看到一个人利用类似二分法的思想，减少了乘法的使用次数。

代码如下：

package irisqp.leetcode;

public class MyPow {
    public double myPow(double x, int n) {
        if (n < 0) {
            return 1 / (myPow(x, -(n + 1)) * x);
        }
        if (n == 0) {
            return 1;
        } else if (n % 2 == 0) {
            return Math.pow(myPow(x, n / 2), 2);
        } else {
            return x * myPow(x, n - 1);
        }
    }

    public static void main(String[] args) {
        MyPow myPow = new MyPow();
        System.out.println(myPow.myPow(0.00001, 2147483647));
    }
}