50. Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−2³¹, 2³¹ − 1]

---

实现幂指数运算。 如果对x连乘n次，时间复杂度为$O(n)$，但使用分治法能降到$O(\log n)$。因为可以把$x^n$分解为： $\begin{equation*} x^n= \begin{cases} x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}, & \text{if } n \text{ even}\\ x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} \cdot x, & \text{if } n \text{ odd} \end{cases} \end{equation*}$

完整代码如下：

class Solution {
public:
    double doPow(double x, int n)
    {
        if (n == 0)
            return 1.0;
        double v = doPow(x, n / 2);
        if (n % 2 == 0)
            return v * v;
        else
            return v * v * x;
    }
    double myPow(double x, int n)
    {
        int m = n > 0 ? n : -n;
        double ans = doPow(x, m);
        return n > 0 ? ans : 1.0 / ans;
    }
};

本代码提交AC，用时3MS。
注意在子程序中不要调用两次doPow(x, n/2)，算出一个v，然后直接v*v即可。

二刷。使用非递归的方法实现快速幂，代码如下：

class Solution {
public:
    double myPow(double x, int n)
    {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        long long m = n; // 先转换为ll，否则n=INT_MIN是有问题
        m = m > 0 ? m : -m;
        double ans = 1;
        while (m) {
            if (m & 1)
                ans *= x;
            m >>= 1;
            x = x * x;
        }
        return n > 0 ? ans : 1 / ans;
    }
};

本代码提交AC，用时3MS。

三刷。注意n=INT_MIN时，第一种解法会有问题，需要用long long存储，代码如下：

class Solution {
public:
	double myPow2(double x, long long m) {
		if (x == 0.0)return 0.0;
		if (x == 1.0 || m == 0)return 1.0;
		if (m == 1)return x;
		if (m < 0) return 1.0 / myPow2(x, -m);

		if (m % 2 == 1)return x * myPow2(x*x, m >> 1);
		else return myPow2(x*x, m >> 1);
	}
	double myPow(double x, int n) {
		return myPow2(x, n);
	}
};

本代码提交AC，用时0MS。