50 Pow(x, n)

Implement pow(x, n).

解题思路

首先给大家介绍一下快速幂算法

以mⁿ为例，可以先将n转换为二进制数，例如

m¹¹ = m^(20+21+23)

再将式子进行一下变形，就可以得到

m¹¹ = m²⁰m²¹m²³

然后我们就可以通过迭代来计算m²ⁱ,这样就可以把算法的复杂度降到O(nlogn)了

举个栗子

以2¹¹为例，我们用变量ans存储结果，用tmp存储2²ⁱ的值

已知：

2¹¹ = 2²⁰2²¹2²³

Step 1:

初始值 ans = 1， tmp = 2²⁰ = 2

Step 2:

因为2¹¹里包含了2²⁰这项,所以ans = ans*tmp = 2, tmp = 2²¹ = tmp * tmp = 4;

Step 3:

因为2¹¹里包含了2²¹这项,所以ans = ans*tmp = 8, tmp = 2²² = tmp * tmp = 16;

Step 4:

因为2¹¹里不包含2²²这项,所以ans保持不变, tmp = 2²³ = tmp * tmp = 256;

Step 5：

因为2¹¹里包含了2²³这项,所以ans = ans*tmp = 2048, tmp = 2²⁴ = tmp * tmp = 65536;

以上，我们就算出了2¹¹的值。mⁿ也是同理~

---

代码

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

PS: 有人会问这里为什么要多此一举转换为long long,是因为我在数据里看到了-2147483648。所以，你懂的~