LeetCode刷题实战50：Pow(x, n)
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 Pow(x, n)，我们先来看题面：
https://leetcode-cn.com/problems/powx-n/
Implement pow(x, n), which calculates x raised to the power n (i.e. xn).
题意
样例
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
解题
https://www.cnblogs.com/techflow/p/12740595.html
的话一定会超时。我们之前讨论过这个问题，即使是运算最快的C++，一秒种内的运算次数也只有10的8次方左右。而32位的int高达10的9次方，如果是Python的话这个运算会更慢，所以我们用循环肯定是无法得出结果的。快速幂
不好求，因为我们现在没什么好的办法，那什么量是容易求的量呢？又该怎么转化呢？顺着这个思路，我们眼前的世界清楚了很多。的方法就是通过循环，每次循环都乘上一个x，循环n次之后得到结果。我们观察一下这个过程，会发现我们在循环的时候，每一次循环，其实都代表了x的指数增加了1。也就是说它是线性增长的，当然就慢了。那什么增长比较快呢？指数增长比较快，比如我们一直翻倍翻倍，就很快。有一个关于指数增长的著名故事，说是从前有一个人发明了国际象棋。当地的国王非常喜欢下棋，于是他就把这个发明者召到了面前来说，你这个发明很好，我愿意奖赏你，你说吧，你想要什么，只要我能给的都行。
颗米。这显然是一个天文数字，别说一个国家了，就是全世界的米加起来也没这么多。故事里没提这个人最后的结局，很有可能因为戏弄国王被砍死了。但不管结局如何，至少说明了一个问题，指数增长和我们的直觉不符，它的变化极快。
，我们再把它平方就得到了
，我们每次平方完，指数都翻了一倍，就好像刚才故事里的棋盘一样。所以我们只需要很少的次数就可以让指数变得很大。
，我们把它放在一边之后还剩下了7，我们再来凑7，又找到了4，于是再放到一边，还剩下3，我们再来凑3……如此循环往复直到凑齐了n为止，n是一定可以这样凑到的，因为这本质上就是一个转化成二进制的过程。
class Solution:
def myPow(self, x: float, n: int) -> float:
base = []
# 标记n是否为负数
flag = n < 0
# 把n置为正数
n = abs(n)
base.append(x)
# 我们算出所有的x^2^i
for i in range(32):
base.append(base[-1] * base[-1])
ret = 1.0
# 遍历32个二进制位
# 如果i位为1，那么答案乘上base[i]
for i in range(32):
if ((1 << i) & n) > 0:
ret *= base[i]
# 如果n为负数返回1/ret
return 1/ret if flag else ret
，然后我们再根据n转化成二进制的结果将它们乘在了一起。当然，我们熟练了之后是可以不这么费劲的，我们可以把这两步合并在一起，我们再来看一段代码：class Solution:
def myPow(self, x: float, n: int) -> float:
base = []
flag = n < 0
n = abs(n)
base = x
ret = 1.0
# 我们在遍历二进制位的时候顺便求出x^2^i
for i in range(32):
if ((1 << i) & n) > 0:
ret *= base
# x^2^i = x^2^(i-1) * x^2^(i-1)
base *= base
return 1/ret if flag else ret
总结
上期推文：
评论