Pow(x,n)

问题

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

实例1：

输入: 2.00000, 10
输出: 1024.00000

实例2：

输入: 2.10000, 3
输出: 9.26100

实例3：

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

我的解法：

class Solution {
    public double myPow(double x, int n) {
        int number = -1;
    
        if(n == 0)
        {
            return 1.0;
        }
        if(n < 0)
        {
            number = -n;
        }
        else
        {
            number = n;
        }
    
    
        double result = 1;
        result = middle(x,number);
        if(n > 0){
            return result;
        }
        else{
            return 1/result;
        }

    public double middle(double x, int number)
    {
        if(number == 1)
        {
            return x;
        }
    
        if(number % 2 == 0)
        {
            return middle(x,number/2)*middle(x,number/2);
        }
        else if(number % 2 == 1)
        {
            return middle(x,number/2)*middle(x,number/2)*x;
        }
        return 1;
    }
}

错误原因：进行了正负号的判断，导致最后增加了处理结果一步，如果结果足够大的情况下，处理结果的步骤相当耗费时间。

标准解法：

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

解法思路：

问题很简单，只是单纯的处理一个幂函数，但是如果简单的使用for循环进行处理，当值很大时，必定会出现耗时极大的问题，这里我们采用递归法折半运算，这会大大降低耗费时间。