超超不会飞

0%

LeetCode25-N次幂

Posted on Views: Valine:

题目

实现 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 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解法一

使用内置函数

1
Math.pow(x, n);

解法二

暴力相乘

x 的 n 次幂，递归为 x x x … x

运行结果：超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public double myPow(double x, int n) {
        if (n > 0) {
            return pow(x, n);
        }
        return 1 / pow(x, n);
    }

    private double pow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (n < 0) {
            return x * pow(x, n + 1);
        }
        return x * pow(x, n - 1);
    }
}

解法三

快速幂 ： 利用分治法的思想，把 n 次相乘一分为二，转成求 x 的 n / 2 次方，再让结果相乘，递归拆分问题，让问题最小化，直到 n=1。

如果n为偶数，则 res = x^n/2^ * x^n/2^

如果n为奇数，则 res = x^n/2^ x^n/2^ x

优化：

  1. 对2取余，可以用二进制 n % 2 == n & 1
  2. 除以2，n / 2 == n >> 1

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double myPow(double x, int n) {
        if (n > 0) {
            return pow(x, n);
        } else {
            return 1 / pow(x, -n);
        }
    }

    private double pow(double x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        double y = pow(x, n / 2);
        if (n % 2 == 0) {
            return y * y;
        } else {
            return y * y * x;
        }
    }
}

循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
     public double myPow(double x, int n) {
        if (x == 0) return 0;
        long b = n;
        double res = 1.0;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b > 0) {
            if ((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

本文首发于我的个人博客 https://chaohang.top

作者张小超

转载请注明出处

欢迎关注我的微信公众号 【超超不会飞】，获取第一时间的更新。