Leetcode第50题

题目描述

https://leetcode.cn/problems/powx-n/

个人思路

纯暴力，累次乘，最后毫无疑问超时。

  public double myPow(double x, int n) {
     double temp=1;
     if(n>=0){
         while (n-->0)temp*=x;

     }else {
         while (n++<0)temp*=1/x;
     }
     return temp;
   }

代码优化

无

参考思路

采用快速幂的思路，例如要求2的8次方，2^8= 2^4 * 2^4,而 2^4 = 2^2 * 2^2 ,2^2 = 2^1 * 2^1 ， 2^1 = 1*2, 这样可以大大缩短计算次数。

public double myPow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        double result = 1.0;
        long absN = Math.abs((long) n);
        while (absN > 0) {
            if (absN % 2 == 1) {
                result *= x;
            }
            x *= x;
            absN /= 2;
        }
        return n < 0 ? 1 / result : result;
}

收获

快速幂这种思路是经常用到的