50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

本题很有意思，如果是一个个乘起来的话那复杂度明显是O(N)。可不可以用比较简单的方法呢，可以的，用二分查找的思想去做这道题。
我们来研究一下如果来做2的十次方，2的十次方是等于4的5次方，16的2次方乘4,256的1次方乘4。
从这个推导过程就能看的出来该怎么做了，如果n可以整除2，那么就直接把x平方，然后n/2，继续做pow(x^{2,n/2)，如果n不能整除2，那么就做pow(x}2,n/2)*x 即可，那显然递归的思想也呼之欲出了，每次递归下去当n=0的时候终止，返回1即可。

代码如下:

class Solution {
    public double myPow(double x, int n) {
        int N = n;
        if(n < 0){
            N = -n;
            x = 1 / x;
        } 
        return fun(x,n);
    }
    public double fun(double x,int n){
        if (n == 0) return 1;
        else{
            double half = fun(x,n/2);
            if (n % 2 == 0)
                return half*half;
            else
                return half*half*x; 
        } 
        
    } 
}

递归就要耗费额外的空间内存，时间复杂度是O（logn）,空间复杂度也是(logn)，可不可以用迭代来代替递归呢，是可以的。
思路上也是一致的与递归。
我们先声明一个 x_temp = x，初始化ans = 1。我们每次迭代都会n除以2，并且判断n是否为偶数，如果是偶数那就不用管直接把x_temp 平方即可，如果是奇数则不但要将x_temp平方，还要将ans乘以此时的x_temp，思路是与之前的一样的。
那我们为什么要用x_temp，回到我们刚刚求2的10次方，我们最后只需要用256乘4即可，我们通过迭代将x平方，再平方的一个过程其实就是已经在求答案了，而在这个过程当中，如果n不是偶数，那就需要乘当时的一个x_temp。那就是答案了，这个过程其实是可以用数学推导出来的。
代码如下：

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N>=0 ? fun(x,N): 1/fun(x,-N);
    }
    public double fun(double x,long n){
        double ans = 1;
        double x_temp = x;
        
        while(n > 0){
            if(n % 2 == 1){
                ans *= x_temp;
            }
            x_temp *= x_temp;
            n /= 2;
        }
        
        return ans;
    } 
}

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