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

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

1.结果

执行结果:通过显示详情>

执行用时:0 ms ,在所有Java提交中击败了100.00%的用户

内存消耗:40.7MB ，在所有Java提交中击败了44.53%的用户

通过测试用例: 304/304

2.时间花费

一个小时，动态规划超内存，实际上并没有二分，相当于遍历一轮

看答案，用递归能过。

3.思路

• 思路一：动态规划

  虽然采用了动态规划，每次按对半相乘，但是还是算了n次，因此时间复杂度是O(n)

• 思路二：递归

  时间复杂度O(log n)

• 快速幂算法

  二分相乘，时间复杂度O(log n)

  主要用到了这个思路，这个很牛逼。分治法思想。

4.code

4.1 code1

class Solution {
    public double myPow(double x, int n) {
        boolean flag = false;
        if (n < 0){
            flag = true;
            n = -n; 
        }
        if( n == 0){
            return 1;
        }else if( n == 1){
            return flag?1/x:x;
        }
        //动态规划 f(n) = f(n/2) * f(n/2)
        // f(0) = 1
        // f(1) = x
        // f(2) = f(1) * f(1)
        // f(3) = f(1) * f(2)
        // f(4) = f(2) * f(2)

        //这里有个整数最大值的问题，应该不要搞到n+1，后面单独乘一次，
        //但是当n为整型最大值时，又会有内存的问题
        double[] re = new double[n];  
        re[0] = 1;
        re[1] = x;
        for (int i = 1; i < n; i++){
            int num = i/2;
            if(i % 2 == 1){
                re[i] = re[num] * re[num + 1];
            }else{
                re[i] = re[num] * re[num];
            }
        }
        // System.out.println(Arrays.toString(re)) ;
        re[n-1] = re[n-1] * x;
        if(flag) return 1/re[n-1];
        else return re[n-1];
    }
}

4.2 code2

略

4.3 code3

这里long N = n;很关键，可以解决指数在整型范围的最大值和最小值问题，

尤其是，最小值**-2147483648**，转正数时会报错

public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

public double quickMul(double x, long N) {
    double ans = 1.0;
    // 贡献的初始值为 x
    double x_contribute = x;
    // 在对 N 进行二进制拆分的同时计算答案
    while (N > 0) {
        if (N % 2 == 1) {
            // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
            ans *= x_contribute;
        }
        // 将贡献不断地平方
        x_contribute *= x_contribute;
        // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
        N /= 2;
    }
    return ans;
}

我自己的代码【效果和答案很接近，时间也是接近0】

 public double myPow(double x, int n) {
        // 使用二分相乘
        // 3^13 = 3x (3^2)^6
        //      = 3x (9^2)^3 = 3x 81^3
        //      = 3x81 x(81^2)^1
        // 也就是先取单，然后底平方，指数减半
        // 以此类推
         if ( x == 1) return x;
         if ( n ==-2147483648 ){
             if (x == -1) return 1;
             else return 0;
        }
        if (n == -2147483648) return 0;
     	boolean flag = false;
        if (n < 0) {
            flag = true;
            // 当n = -2147483648时，取绝对值，会超过整型范围
            n = -n;
            System.out.println(n);

        }
        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return flag ? 1 / x : x;
        }
        double result = 1;
        double base = x;
        System.out.println("result" + "\t\t" + "base" + "\t\t" + "n");
        while (n > 1) { //这里可以大于0，然后省掉return上面那句
            if (n % 2 == 1) {
                // 表示是奇数，出一个底，更新指数
                result = result * base;
                n = n - 1;
            } else {
                // 表示指数是偶数，底平方，指数减半
                base = base * base;
                n = n / 2;
            }
            System.out.println(result + "\t\t" + base + "\t\t" + n);
        }
        result = result * base; // while(n > 0)时，可省略这句
        return flag ? 1 / result : result;

    }