50 Pow(x, n)

本文最后更新于：2021年7月12日 下午

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

示例 1：

1
2
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

1
2
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

1
2
3
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • -104 <= xn <= 104

Solution

参考：LeetCode官方 ，方法同 372 超级次方

  • 快速幂
  • 需要注意的细节较多

第一版：超时

未通过示例：

0.00001 2147483647

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            x = 1 / x;
            n = -1 * n;
        }
        if (n & 1 == 1) {
            return x * myPow(x, n-1);
        } else {
            return myPow(x, n/2) * myPow(x, n/2);
        }
    }
};

第二版：执行错误

未通过示例：

1.00000 -2147483648 （-1 * n 会超出int）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            x = 1 / x;
            n = -1 * n;
        }
        double res = 1;
        while (n) {
            if (n & 1) {
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
};

第三版：迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        long long N = n;
        if (n < 0) {
            x = 1 / x;
            N = -1 * N;
        }
        double res = 1;
        while (N) {
            if (N & 1) {
                res *= x;
            }
            x *= x;
            N >>= 1;
        }
        return res;
    }
};

第四版：递归法，时间要慢很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        long long N = n;
        if (n < 0) {
            x = 1 / x;
            N = -1 * N;
        }
        if (N & 1 == 1) {
            return x * myPow(x, N-1);
        } else {
            double y = myPow(x, N/2);
            return y * y;
        }
    }
};
algo leetcode 递归 数学

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！