Lintcode428 Pow(x, n) solution 题解

【题目描述】

Implement pow(x, n).

 Notice

You don't need to care about the precision of your answer, it's acceptable if the expected answer and your answer 's difference is smaller than 1e-3.

实现 pow(x,n)

 注意事项

不用担心精度,当答案和标准输出差绝对值小于1e-3时都算正确

【题目链接】

www.lintcode.com/en/problem/powx-n/

【题目解析】

本题的题目描述很简单,计算x的n次幂。n为int,即[-2147483648, 2147483647]之间。

对于n的负数的情况,可以知道 x^n = 1 / x ^(-n)。所以我们只需要求出x^abs(n),再根据n的正负号做最后一步计算。由于abs(-2147483648)超过了int的范围,所以我使用了long long来存储。

接下来考虑如何计算x^n,以下默认n为正整数:首先可以肯定得是直接使用For循环对n进行枚举显然是不行的。我们要想办法对x^n进行拆分,有: 

x^n = x^(2^0*t[0]) * x^(2^1*t[1]) * ... * x^(2^k*t[k]) + ... (t[0..k] =1or0

并且在这此基础上我们有 x^(2^k) * x^(2^k) = x^(2^(k +1))

利用这个性质,我们可以再O(log n)的时间内求出所有的x^(2^k),当2^k>n时,就停止。而对于t[i],我们可以对n进行二进制的拆分,同样在O(log n)的时间内求出t[0]..t[k]。再将对应的数位相乘就可以得到我们的x^n,举个例子来说当p=2,n=5时:n =5= (101)2

则可以计算出t[0]=1, t[1]=0,t[2]=1。那么有 2^5=2^(2^0*1) *2^(2^1*0) *2^(2^2*1) =2^1*2^0*2^4=2^5

在总时间复杂度O(log n)的情况下也就求出了x^n。

【参考答案】

www.jiuzhang.com/solutions/powx-n/

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 晚归,巴士,专车
    谦与芊寻阅读 314评论 0赞 0
  • 风拍打着铁屋楼顶 不知名的鸟胡乱的回应 我舍不得熄的 是那串想亮给你看的灯 另一盏灯下,另一个晚上 你的笑意给我的...
    二向箔倩阅读 534评论 2赞 5
  • 十一小长假,第一天,和驴友们组织去穿越香巴拉!这叫个兴奋啊!
    努力奔跑的小喵阅读 629评论 0赞 2
  • 今天开始是我第一次写简书,你很难想象一个念书时候作文从没写过800字作文的人会想着要发表简书文章!!还是想要发表一...
    宇墨阳阅读 432评论 0赞 0

友情链接更多精彩内容