[C++] LeetCode 50. Pow(x, n)

题目

实现 pow(x, n)。

示例 1:

输入: 2.00000, 10 输出: 1024.00000

示例 2:

输入: 2.10000, 3 输出: 9.26100

解析

这个题目有较多细节需要注意，容易导致错误。

1、n可能为负值，此时需要考虑取绝对值

2、由于n为有符号整型变量，范围为-2147483648～2147483647，取最小值时，如果取绝对值会导致溢出。

具体解法有两种较好的

方法一

利用二进制方法，将n用二进制展开，例如求 25 2 5 ，其中 5=101(2)=1∗22+0∗21+1∗20 5 = 101 ( 2 ) = 1 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 ，故 25=21∗22+0∗21+1∗20=51∗22∗50∗21∗51∗20 2 5 = 2 1 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 = 5 1 ∗ 2 2 ∗ 5 0 ∗ 2 1 ∗ 5 1 ∗ 2 0

从上述例子可以看出，可以把n写成二进制，对应位为1时，则乘以当前值，否则不乘；

具体代码如下：

class Solution {
public:
    double myPow(double x, int n) {
        double ans=x,res=1.0;
        long long m=n;
        m=abs(m);
        while(m>0){
            if(m&1==1) res*=ans;
            m=m>>1;
            ans*=ans;
        }
        if(n>0)
            return res;
        else
            return 1.0/res;
    }
};           

方法二 分治法

代码

class Solution {
public:
    double getRes(double x,long long n){
        if(n==0) return 1;
        else if(n==1) return x;
        if(n%2==0) {
            double tmp= getRes(x,n/2);
            return tmp*tmp;
        }
        else return getRes(x,n-1)*x;
    }
    double myPow(double x, int n) {
        long long m=n;
        m=abs(m);
        double res=getRes(x,m);
        if(n>0)
            return res;
        else
            return 1.0/res;
    }
};