RBA的技术分享

题目:
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最开始想到的是一个一个的乘. 而且知道栈的递归解法比较慢. 使用了如下的迭代方法.简单规避了负数的处理.以及-n在最小 n值的时候.可能出现的负数问题.

简单思路是:

• n为正数的时候实际是 x*x*x*x...x一直乘下支.
• n为负数的时候,实际为 (1/x)*(1/x)*(1/x)*.....*(1/x)
  这样一直 for循环就好了.

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

执行结果肯定是超时了. 在很大的数的时候. 这个循环次数还是比较可观的. 也就可能 10亿次吧. 虽然一般的 cpu 几秒完成不成问题.这个是我在我自己的mac上的测试数据:

use:3465 ms

public static void main(String[] args) {
        Long start = System.currentTimeMillis();
        new Solution().myPow(1.00000, 2147483647);
        System.out.println("use:" + (System.currentTimeMillis() - start) + " ms");
    }

那先2分试试?

2^n = 2^(n/2)*2^(n-n/2)

这样似乎能够快一些. 毕竟我能够比较快的到 n-> 1;试试

use:8913 ms
这个时间实际更长了. 纠其原因是.下面有大量的重复计算. 反而更慢了. 每分一次最后都要重复计算一次最小的幂.

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

        if(n>1){
            return myPow(x, n/2)*myPow(x,n-n/2);
        }
        return 1;
    }
}

正确解法:

猜测: 如果我能够快速的计算一个2的整数次方的一个 n' 那我就可以先计算 n'的幂.然后再计算剩下的n-n'这样看起来会更快的逼近正确值. 但是在计算的过程中:

• n' 的计算的过程中的最后的起始位置的计算是包含后面的n-n'部分是有重复的. 比如 n=13需要计算 8+2+1的次幂. 这样8的计算包含2的计算,2的计算包含1的计算.
• 但是如果反过来计算可以先计算1,再计算2,再计算8.那后面的计算就可复用前面的结果.
• 写到这里. 对于怎么去拆分 n 呢.实际 n 的2进制表示已经给出了答案.
• n的二进制表示为: 101010100101...101这样哪一位上不为零就包含这个整数次幂的积.而从最低位开始计算. 往左一位的积正好是上一位的平方.为什么这么说呢.这个序列从低位开始表示为:

1  2  4 8 16 32 64

实际即: 2^0,2^1,2^2 然后这个是表示的 n 的值的部分. 这个值每次会*2 那刚好是原来的数的平方.

use:1 ms

// 把 n 拆分成一个2的 k 次方的和.
// 把 n 表示成二进制.
// 然后 n =  101000010101 , 大概如是这样表示的数据.
// 那 n = a0*2^0+a1*2^1+a2*2^2+ ... + a31*2^31  (先只研究正数)
// 由于 x^(a+b) = x^a*x^b.
// 所以 x^n = x^(a0*2^0)*x^(a1*2^1) * ... * x^(a31*2^31)
// 里面的 a0-a31都是要么为0,要么为1的系数.
// 而某一个数的值.正好是上一个值的平方.
// 这样只需要计算 a^0 , a^1 , a^2 , a^4 .... a^(2^31) 这几个数即可.

class Solution2 {
        public double myPow(double x, int n) {
            if(n<0){
		// 特殊处理最小值.因为最小值没有最大的正数与之对应
                if(n == Integer.MIN_VALUE){
                    return (1/x)*myPow(1/x,Integer.MAX_VALUE);
                }
                return myPow(1/x,-n);
            }
            if(n == 0){
                return 1;
            }

            double r = 1.0;
            double p = x;
            for(int i=0;i<31;i++){
                if( ( n & (1<<i) ) > 0){
                    r *= p;
                }
                p = p * p;
            }
            return r;
        }
    }