16-数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

第一种 根据定义计算

根据幂的定义来计算。

  public double Power(double base, int exponent) {
        int absExp = Math.abs(exponent);
        double result = 1.0;
        for (int i = 0; i < absExp; i++) {
            result *= base;
        }
        if (exponent < 0) {
            result = 1 / result;
        }
        return result;
    }

以上程序可以通过牛客的测试用例，不过没有对base exponent的范围进行开考虑和限制。

leetcode里需要考虑给出的n是Integer.MIN_VALUE的情况，该算法未考虑。

第二种 递归计算

考虑2^5，相当于 (2^2) * (2^2) * 2，也就是我们将exponent使用折半计算在相乘的技巧减少计算的次数。下面先用递归实现这种技巧。

private Map<Long, Double> memo = new HashMap<>(); //使用备忘录缓存中间结果
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        long k =  n; //这里注意假如n是Integer.MIN_VALUE，则Math.abs(n)返回的依然是Integer.MIN_VALUE，所以要提高到long。
        boolean isNegative = k < 0;
        k = Math.abs(k);
        double result = myPowCore(x, k);
        if (isNegative) {
            return 1 / result;
        }
        return result;
    }

    private double myPowCore(double x, long n) {
        if (n == 1) {
            return x;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        double result = 0.0;
        if (n % 2 == 0) { //假如是偶数，就可以折半计算。
            result  =  myPowCore(x, n / 2) *  myPowCore(x, n / 2);
        }else{
          //如果不是偶数，就变成偶数
            result =  x * myPowCore(x, (n - 1));
        }
        memo.put(n, result);
        return result;
    }

第三种 快速幂算法

$$ x^n = (x²⁾(n/2) $$

我们使用迭代来实现快速幂。

   public double myPow(double x, int n) {
        if(Math.abs(x - 0 ) < 0.000001){
            return 0.0;
        }
        if(n == 0){
            return 1.0;
        }
        long b = n;
        b = Math.abs(b);
        double res = 1.0;
        while(b != 0){
            if((b & 1) == 1){ //如果是基数，就简单的去掉一个x，也就是res = res * x;
                res *= x;
            }
            //
            x *= x;
            b >>>= 1;
        }
        return n > 0 ? res : 1.0 / res;
    }