友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

50. Pow(x, n)

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

示例 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

提示:

  • -100.0 < x < 100.0

  • -231 <= n <= 231-1

  • n 是一个整数

  • 要么 x 不为零,要么 n > 0

  • -104 <= xn <= 104

思路分析

0050 01
0050 02

首先,可以把"一半的计算结果"存储起来,节省一半的递归调用;

其次,没想到还需要处理"无穷"的情况!

另外,思考一下,如果使用迭代来实现?

快速幂的算法能看懂,但代码不知道怎么写。

  • 一刷

  • 二刷

  • 三刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Runtime: 1 ms, faster than 94.10% of Java online submissions for Pow(x, n).
 *
 * Memory Usage: 34.4 MB, less than 5.88% of Java online submissions for Pow(x, n).
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-13 21:19
 */
public double myPow(double x, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }

    double semiResult = myPow(x, n / 2);
    if (Double.isInfinite(semiResult)) {
        return 0.0;
    }

    return (n % 2 == 0 ? 1.0 : x) * semiResult * semiResult;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-15 17:13:46
 */
public double myPow(double x, long n) {
  if (x == 0) {
    return 0;
  }
  if (n == 0) {
    return 1;
  }
  if (n == 1) {
    return x;
  }
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }
  double tmp = myPow(x, n / 2);
  return tmp * tmp * ((n & 1) == 0 ? 1 : x);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-07 14:26:30
 */
public double myPow(double x, long n) {
  if (x == 0) {
    return 0;
  }
  if (n == 0) {
    return 1;
  }
  boolean negative = n < 0;
  n = Math.abs(n);
  double result = 1;
  double bin = myPow(x, n / 2);
  if (n % 2 == 1) {
    result = x * bin * bin;
  } else {
    result = bin * bin;
  }
  return negative ? 1 / result : result;
}