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

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
示例 1:
输入: 2.00000, 10
输出: 1024.00000

题解思路：
最直观的解法就是将x重复乘n次。因为乘法是可交换的，所以可以将n次相乘转换为两个n/2次相乘的结果乘积，由于两半的计算是一样的，所以只需要执行一次就可以。而且对于新拆开的计算，又可以继续拆开，这就是分治思想。
image.png

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.        boolean isNegative=false;
  4.        if(n<0){
  5.            n=-n;
  6.            isNegative=true;
  7.        }
  8.        long y=b;            *****
  9.        double res=pow(x,y);
  10.        return isNegative?1/res:res;
  11.     }
  13.     private double pow(double x,int n){
  14.         if(n==0) return 1;
  15.         if(n==1) return x;
  16.         double res=pow(x,n/2);
  17.         res=res*res;
  18.         if(n%2!=0)
  19.             res*=x;
  20.         return res;
  21.     }
  22. }

总结： 分治思想在于一步一步的将问题细分下去，递归的思想正好满足这个条件。更多细节的地方：如果是负次方，直接转换为除法，如果是奇数次方，再乘一次解决。 注：Java 代码中 int32 变量 n \in [-2147483648, 2147483647]n∈[−2147483648,2147483647] ，因此当 n = -2147483648n=−2147483648 时执行 n = -nn=−n 会因越界而赋值出错。解决方法是先将 nn 存入 long 变量 bb ，后面用 bb 操作即可。