【DFS】春来我不先开口,哪个虬儿敢做声

1. 快速幂

题目链接: 50. Pow(x, n)

题目内容:

实现 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

解法一: 暴力枚举 循环遍历n, x在循环中自乘, 如果n太大,则会超出时间限制.

解法二: 递归实现快速幂

举两个例子讲清楚快速幂的原理 假设x = 3; 1. 当n为偶数时:

当n为偶数时, 3^n = 3 ^n/2 * 3^n/2; 2. 当n为奇数时:

当n为奇数时3^n = 3 ^n/2 * 3^n/2 * 3

综上所述, 不难得出递归出口即为,当n = 0时,返回1即可.

代码实现

代码语言：javascript代码运行次数：0运行复制
class Solution {
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x,-n) : pow(x,n);
    }
    public double pow(double x, int n) {
        if(n == 0) return 1.0;
        double tmp = pow(x,n/2);
        return n % 2 == 0 ? tmp*tmp : tmp*tmp*x;
    }
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-18，如有侵权请联系 cloudcommunity@tencent 删除double遍历递归原理dfs