Pow(x,n)

来源Leetcode第50题Pow(x,n)

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

说明:

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

暴力求解

常规思路还是暴力，快速幂这种东西大一的时候接触过，但是已经忘了，先试试暴力能不能过

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
		//要处理负指数将底数转变成倒数即可
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        for (long i = 0; i < N; i++)
            ans = ans * x;
        return ans;
    }
}

二分查找

很尴尬，超时了，在第291/304个用例的时候TLE了
查看题解，有题解采用了二分查找的思路，将指数分解为n/2和n%2，然后一直递归下去。

public double myPow(double x, int n) {
    if (n == 0) { return 1; }
    if (n == 1) { return x; }
    if (n == -1) { return 1 / x; }
    double half = myPow(x, n / 2);
    double rest = myPow(x, n % 2);
    double total = rest * half * half;
    return total;
}

---

2019年10月31日更新：

快速幂

首先令b = p0*2^k + p1*2^k-1 + … + pk*2^0;
则a^b = a^p0*2^k * a^p1*2^k-1 * … * a^pk*2^0;

代码如下：

class Solution {
    public double myPow(double x, int n) {
    long N = n;	
	if(n < 0)
	{
	//要处理负指数将底数转变成倒数即可
        x = 1 / x;
        N = -N;
	}
	
    double ans = 1,base = x;// ans：幂的结果；base：底数X
	
    while(N != 0)
    {
        if(N % 2 != 0)
        {
		//这一步对应的就是求N的二进制位的最低位
        ans = ans * base;
        }
        base = base * base;
        N = N >> 1;
    }
    return ans;
    }
}