LeetCode-50-Pow(x, n)

1、递归

我们最简单的思路就是使用递归，每次就让x乘上Pow(x, n-1)的值。但是这样做的缺点在于递归时间过长会导致超时，因此我们可以使用快速幂进行优化。

快速幂的思想在于我们在求x的N次幂时，不使用$x\ast x^{N-1}$，而是使用$x^{N/2}\ast x^{N/2}$从而减少递归次数至$O(logN)$。

class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、迭代

我们可以将$x^n$拆成多个$x^{2^k}$项之和，例如$x^{7}7=x^1\ast x^4\ast x^8\ast x^{64}$，而77的二进制表示恰好为$1001101$，其中二进制上每个1的位置表示了有哪些$x^{2^k}$需要相加，我们可以基于这一特点来设计迭代过程。

class Solution {
public:
    double quickMul(double x, long long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25