【题目描述】
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。
【参考答案】
网友评论