LC50 Pow(x,n)

LC50

实现 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 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

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

思路1：

1）如果n<0，结果取倒数

2）把幂次函数想象成加法。递归时：

n为偶数，则为n/2+n/2（x部分是相乘的）

n为奇数，则为n/2+n/2+1

因为分解成n/2，所以复杂度下降到logn

递归法

class Solution {
public:
    double myPow(double x, int n) {
        if(n==1)
        return x;
        if(n==0)
        return 1;
        int tmpn=n;
        n=abs(n);
        double res=0.0;
        double temp=myPow(x,n/2);
        if(n%2==0){
          
            res=temp*temp;
        }else{
            
            res=temp*temp*x;
        }
        if(tmpn<0)
        res=1/res;
        return res;

    }
};

时间复杂度：O(\log n)O(logn)，即为递归的层数。

空间复杂度：O(\log n)O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路2：

作者：jyd
链接：https://leetcode-cn.com/problems/powx-n/solution/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二进制角度

对于任何十进制正整数n，设其二进制为“”(为二进制某位值，),则有：

• 二进制转十进制：n=(即二进制转十进制公式)；
• 幂的二进制展开：

而任意十进制数都可以用二进制表示。

因此可以把计算转化为其它问题：

• 计算的值，计算时循环赋值，平方计算即可。
• 获取n转换为二进制的值。即。

【十进制如何转二进制】

[判题过程巨慢 不知道为什么]

class Solution {
public:
    double myPow(double x, int n) {
        if(n==1)
        return x;
        if(n==0)
        return 1;
        int tmpn=n;
        n=abs(n);
        double res=1.0;
        double temp=x;
        while(n>0){//理由除法余数得到二进制数。
            if(n%2==1){
                res=res*temp;
            }
            temp=temp*temp;
            n=n/2;
        }

        if(tmpn<0)
        res=1/res;
        return res;

    }
};