LeetCode50-Pow(x, n)

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/powx-n/

中文链接：https://leetcode-cn.com/problems/powx-n/

题目详述

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

示例 1:

1
2
输入: 2.00000, 10
输出: 1024.00000

示例 2:

1
2
输入: 2.10000, 3
输出: 9.26100

示例 3:

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

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

题目详解

分治。讨论 n >= 0 的情况（若 n < 0 转化为正数即可）：

  • 若 n 为偶数，则 pow(x, n) = pow(x * x, n / 2)。
  • 若 n 为奇数数，则 pow(x, n) = x * pow(x * x, n / 2)。
  • 终止条件为 n == 0 时 return 1。
  • 可以很容易写出递归形式，改成迭代形式也很简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00050 {

    public double myPow(double x, int n) {
        // int 型 −2^31 取负数会溢出，仍然是 −2^31，转换为 long 防溢出
        long y = n;
        // 将负幂转化为正幂计算
        if (y < 0) {
            x = 1 / x;
            y = -y;
        }
        double res = 1;
        while (y != 0) {
            if ((y & 1) == 1) {
                res *= x;
            }
            x *= x;
            y >>= 1;
        }
        return res;
    }
}