剑指 Offer 16. 数值的整数次方

题目

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 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

题目解析

通过递归实现迭代乘法，同时判断负数。本题为中等难度，非常好的题目。

第一次实现

使用递归，并判断正负，Test case 次方非常大，提交失败爆栈。

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

第二次

尝试使用动态规划，空间复杂度无法满足。

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        boolean isNagetive = n < 0;
        n = n > 0 ? n : -n;
        double[] dp = new double[n];
        dp[0] = x;
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] * x;
        }
        return isNagetive ? 1 / dp[n-1] : dp[n-1];
    }
}

第三次

好像思路有问题，可以不使用递归和动态规划，时间复杂度无法满足，Case 为 0.00001, 2147483647

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        boolean isNagetive = n < 0;
        n = n > 0 ? n : -n;
        double result = x;
        for (int i = 1; i < n; i++) {
            result = result * x;
        }
        return isNagetive ? 1 / result : result;
    }
}

第四次

算法这种东西写又写不会，写了又爆栈溢出，只能靠抄袭勉强维持生活的样子.........
通过递归 + 折半解决乘积计算时间过程问题。来自用户 https://leetcode-cn.com/u/asche/

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

C++ 快速幂实现

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        //考虑到负数右移永远是负数，
        if(n==-1) return 1/x;
        if(n&1) return myPow(x*x, n>>1)*x;
        else return myPow(x*x, n>>1);
    }
};