Clarklevis' Workshop.

【LeetCode】 数值的整数次方

LeetCode
字数统计: 366阅读时长: 1 min
2021/08/21

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

1
2
3
4
5
6
7
输入：x = 2.00000, n = 10
输出：1024.00000
输入：x = 2.10000, n = 3
输出：9.26100
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

超时做法：简单的循环求解（递归会栈溢出）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        double res = 1;
        int absN = Math.abs(n);
        while(absN > 0){
            res *= x;
            absN--;
        }
        if(n>0) return res;
        return 1/res;
    }
}

快速幂方法：

所谓的快速幂法就是将指数变为二进制的形式：

\[x^n=x^{1b_1 + 2b_2 + 4b_3 + ... + 2^{m-1}b_m}\]

其中的 \(b_1,b_2, ..., b_m\)为二进制位上的「0，1」

所以只需要循环遍历整个指数部分就以：

  • 计算\(x^1, x^2,...x^{2^{m-1}}\)的值：循环赋值操作：\(x = x^2\)
  • 获取\(b_1,b_2, ..., b_m\)：
    • n&1（和1做与）：判断最后一位是不是1，是1的话，就可以res = res * x ，否则不是1，就保持原来的res不变
    • n>>1（向右位移）：判断下一位是不是1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        double res = 1;
        long b = n; //考虑到n的相反数可能越界
        if(b<0){
            x = 1/x;
            b = -b;
        }
        while(b > 0){
//按位和1做&
            if((b & 1) == 1) res *= x;
            x *= x;
            b = b >> 1;
        }
        return res;
    }
}
CATALOG
Total : 7
2021
Android LeetCode 剑指offer 面经