力扣_50之x的n次幂

发表于 分类于 评论数： 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/powx-n

方法1：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double myPow1(double x, int n) {
    double res=1.00000;
    //判断0次幂和1的任何次幂；
    if(n==0||x==res){
        return res;
    }
    //判断-1的n次幂
    if(x*-1==res){
        return n%2==0?1:-1;
    }
    //判断最小次幂及0的n次幂
    if(n==-2147483648||x==0){
        return res*0;
    }
    //迭代求n次幂
    int len=n<0?n*-1:n;
    for(int i=0;i<len;i++){
        res=res*x;
    }
    //返回结果
    return n<0?1.0/res:res;
}

耗时：2484ms

方法2：快速幂 + 递归(官方)

「快速幂算法」的本质是分治算法。
举个例子，如果我们要计算 x64，我们可以按照：x→x2→x4→x8→x16→x32→x64的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x64的值，而不需要对 x 乘 63 次 x。再举一个例子，如果我们要计算 x77，我们可以按照：x→x2→x4→x9→x19→x38→x77的顺序，在 x→x2，x2→x4，x19→x38这些步骤中，我们直接把上一次的结果进行平方，而在 x4→x9，x9→x19，x38→x77这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：

  • 当我们要计算 xn时，我们可以先递归地计算出 y=x⌊n/2⌋，其中 ⌊a⌋ 表示对 a 进行下取整；
  • 根据递归计算的结果，如果 n 为偶数，那么 xn=y2；如果 n 为奇数，那么 xn=y2×x；
  • 递归的边界为 n=0，任意数的 0 次方均为 1。
    由于每次递归都会使得指数减少一半，因此递归的层数为 O(logn)，算法可以在很快的时间内得到结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public double myPow(double x, int n) {
    long N = n;
    return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}

public double quickMul(double x, long N) {
    if (N == 0) {
        return 1.0;
    }
    //分治法
    double y = quickMul(x, N / 2);
    //判断奇偶次幂
    return N % 2 == 0 ? y * y : y * y * x;
}

耗时：<1ms