题目难度：中等

题目描述：

实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：

 1.保证base和exponent不同时为0。
 2.不得使用库函数，同时不需要考虑大数问题
 3.有特殊判题，不用考虑小数点后面0的位数。

数据范围：,保证最终结果一定满足

进阶：空间复杂度 O(1) ，时间复杂度 O(n)

示例1:

输入：2.00000,3
返回值：8.00000

示例2:

输入：2.10000,3
返回值：9.26100

思路1：“暴力枚举”

时间复杂度：O(n)

class Solution {
public:
  double Power(double base, int exponent) {
      if (base == 0) return 0;
      if (exponent == 0) return 1;
      double res = 1;

      if (exponent < 0) {
          base  = 1 / base;
          exponent = -exponent;
      }

      while (exponent--) {
          res *= base;
      }

      return res;
  }
}

思路2：分治

可以观察到： ,
所以，可以按照指数奇偶，逐步计算
时间复杂度：O(logn)

class Solution {
public:
  double Pow(double base, int exponent) {
      if(exponent == 0) return 1;
      if(exponent < 0) {
          base = 1 / base;
          exponent = -exponent;
      }
      return PowHelper(base, exponent);
  }

  double PowHelper(double b, int e) {
      if(e == 1) return 1;
      double res = PowHelper(b, e / 2);
      if(e & 1) {
          // 奇数
          return res * res * b;
      } else return res * res;
  }
}

思路3：快速幂

时间复杂度：O(logn)

class Solution {
public:
  double Power(double base, int exponent) {
      if (exponent == 0) return 1;

      if (exponent < 0) {
          base = 1 / base;
          exponent = -exponent;
      }

      while (exponent) {
          if (exponent & 1) res *= base;
          base *= base;
          exponent >>= 1; 
      }
      return res;
  }
}

😘😘😘😘😘😘😘😘😘😘😘😘😘