实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
「快速幂算法」的本质是分治算法。
以示例为例,从 2 开始,每次直接把上一次的结果进行平方,计算3次就可以得到2的10次方值,我们可以按照:
直接从左到右进行推导看上去很困难,因为在每一步中,我们不知道在将上一次的结果平方之后,还需不需要额外乘 x。但如果我们从右往左看,分治的思想就十分明显了。
代码如下:
由于递归需要使用额外的栈空间,我们试着将递归转写为迭代。
我们以 x 的77次方 作为例子:
可以发现:
我们把这些贡献相乘,x * x的4次方 * x的8次方 * x的64次方 恰好等于 x的77次方。而这些贡献的指数部分又是什么呢?它们都是 2 的幂次,这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1,4,8 和 64,恰好就对应了 77 的二进制表示 (1001101)2 中的每个 1!
这样以来,我们从 x 开始不断地进行平方,如果 n 的第 k 个(从右往左,从 0 开始计数)二进制位为 1,那么我们就将对应的贡献
x的(2的k次方)次方 计入答案。
代码如下:
本文内容出处是力扣官网,希望和大家一起刷算法,在后面的路上不变秃但是变强!
好兄弟可以点赞并关注我的公众号“javaAnswer”,全部都是干货。
留言与评论(共有 0 条评论) “” |