题意
实现 pow(x, n)
,即计算 x 的 n 次幂函数。
示例 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
说明:
- -100.0 < x < 100.0
- n 是 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1] 。
思路
当指数为负数的时候,可以转化为底数取倒数,指数取相反数的情况,这一点并不难理解。
为了避免一次又一次将底数相乘,我们采用这样「偷懒」的策略,比如要计算 5^18,其实我们只要计算出 5^9,然后再自己乘自己就好了,这样做可以避免做 9 次乘5的运算。
那么有一种机制就能帮助我们找到一个整数的合适的「分解」,那么就是将一个整数看成它的二进制形式。
于是,我们可以把指数 做「二进制分解」,在底数不断自身乘以自身的过程中,将最终结果需要的部分保存下来。
代码
class Solution {
public boolean myPow(double x, int n) {
int pow = Math.abs(n);
double res = 1;
for (int i = pow; i != 0; i >>= 1) {
if (i % 2 != 0) {
res *= x;
}
x *= x;
}
return n < 0 ? 1/res : res;
}
}