剑指 Offer 16. 数值的整数次方
文章目录

题目

实现  pow(x,  n)  , 即计算 x 的 n 次幂函数 (即, xn) . 不得使用库函数, 同时不需要考虑大数问题.

示例 1:

1
2
输入:x = 2.00000, n = 10
输出:1024.00000

示例 2:

1
2
输入:x = 2.10000, n = 3
输出:9.26100

示例 3:

1
2
3
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

提示:

1
2
3
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104

链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

题解

普通解法: 无脑循环, 肯定会 TLE

优化1

  1. 如果 $n>0$, 计算 $x^n$

    • $x^n = (x^{n \over 2})^2$
    • 如果 n 为单数, 可以计算 $x^n = x * x^(n-1)$
    • 如果 n 为偶数, 可以计算 $x^n = x^{n \over 2}* x^{n \over 2}$
    • 然后上述可以进行递归
  2. 如果 $n<0$ 直接计算 $(1/x)^n$ 同样带入递归

  3. 如果 $n===0$ 直接返回 1

以上复杂度 $O{n \over 2}$ 还是不够

优化2

快速幂方法

$x^{11} = x^{2^3+2^1+2^0} = x^{2^3} * x^{2^1} * x^{2^0} = x^8 * x^4 * x^1$

也就是根据幂次数 11 , 转化为二进制数 1101b, 然后只需要求二进制数字为 1 的位置对应的权重然后相乘即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

var myPow = (x, n) => {
if (n === 0) return 1;
if (n === -2147483648) return myPow(x, n / 2) * myPow(x, n / 2);
if (n < 0) return myPow(1 / x, -1 * n);

let flag = n;
let res = 1;
while (flag > 0) {
if (flag & 1) {
res = res * x;
}
x = x * x;
flag = flag >> 1;
}

return res;
};

一个坑

使用快速幂方法