@TOC

剑指offer 16 数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: $2^{-2} = 1/2^2 = 1/4 = 0.25$

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [$−2^{31}, 2^{31} − 1$] 。

注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

解法一：暴力解法

解法一：暴力解法（不推荐，效率太低，太low了），即先判断exponent正负，取绝对值后，让base乘以自身exponent次即可，最后根据开始exponent的正负情况返回1/res或者res。

解法二：分治思想

分治思想，因为乘法是可交换的，所以可以将上述操作拆开成两半(x * x..x) (x * x..x)，两半的计算是一样的，因此只需要计算一次。而且对于新拆开的计算，又可以继续拆开。这就是分治思想，将原问题的规模拆成多个规模较小的子问题，最后子问题的解合并起来,时间复杂度变为$O(logn)$。

n为8时的分治过程如图：

本题中合并时将子问题的解乘以自身即可。但如果 n 不为偶数，那么拆成两半还会剩下一个 x，此时在将子问题合并时还需要多乘一个 x。

公式这里显示不出来，请看本人博客 16. 数值的整数次方： https://blog.csdn.net/YouMing_Li/article/details/114278712

$$x^n=\left\{ \begin{aligned} x^\frac{n}{2} * x^\frac{n}{2} && n\bmod2=0 \\ x*(x^\frac{n}{2} * x^\frac{n}{2}) && n\bmod2=1 \end{aligned} \right. $$

Java代码

class Solution {
    public double myPow(double x, int n) {
        /*主要是要考虑指数为负数时结果要取倒数
        然后分奇偶使用递归将计算将过程减半*/
        double res = 1;
        int num = Math.abs(n);
        if(n > 0){
            return pow(x,num);
        }else{
            return 1/pow(x,num);
        }
    }
   public double pow(double x,int n){
       if(n == 0){
           return 1;
       }
       //分治（类似归并排序中的左右mergeSort,只是这里左右两边一样，故只要写一个）
       double y = pow(x,n/2);

       //合并（类似归并排序中的merge阶段）
       if(n % 2 == 0){
          return y*y;
       }else{
           return y*y*x;
       }
   } 
}

解法三：快速幂

快速幂的介绍可以参考本人博客day27 89 a^b （快速幂）：https://blog.csdn.net/YouMing_Li/article/details/113934215

Java代码

class Solution {
    public double myPow(double x, int n) {
        //快速幂解法
        double res = 1;
        boolean flag = n < 0;
        n = Math.abs(n);
        while(n != 0){
           if((n & 1) != 0) res *= x;
            x *= x;
            n >>= 1;
        }
        if(flag){
            return 1 / res;
        }
        return res;
   } 
}

当n为负无穷时，取绝对值会超出int范围,即使转成long也会出现如下报错。但这里还是将代码贴出来了，因为思路是完全正确的，就当复习一下快速幂吧。