LeetCode日常-简单-实现pow(x, n)

本文最后更新于：2020年9月27日 晚上

题目

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

1
2
3
示例 1:
输入: 2.00000, 10
输出: 1024.00000
1
2
3
示例 2:
输入: 2.10000, 3
输出: 9.26100
1
2
3
4
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

自解

简单递归，一次次乘，得到结果。

官方解法-快速幂算法

思路

假设我们已经得到了 $$x ^ {n / 2}$$ 的结果，现在想要计算 $$x^n$$ 的结果
设 A 是 $$x^{n/2}$$ 的结果，我们可以分别根据 n 的奇偶来讨论 $$x ^ n$$

  • 如果 n 是偶数，我们可以使用公式 $$(x^n)^2 = x^{2n}$$ 得到 $$x^n = A^2$$
  • 如果 n 是奇数，那么 $$A^2 = x^{n-1}$$

直观地说，我们需要将另一个 x 和结果相乘，所以 $$x^n = A * A * x$$ 。这种方法可以很容易地用递归实现
我们称这个方法为“快速幂（Fast Power）”，因为我们最多只需要 O(log(n)) 次计算就可以得到 $$ x^n $$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def fastpow(self, x: float, n: int):
        if n == 1: 
            return x
        return self.fastpow(x, n/2)**2 if n%2 == 0 else self.fastpow(x, (n-1)/2)**2 * x

    def myPow(self, x: float, n: int) -> float:
        if n < 0: 
            x = 1/x
            n = -n
        elif n == 0:
            return 1
        return self.fastpow(x, n)