快速幂算法原理及 Java 实现

本文讲解快速幂的解法技巧，后续文章会涉及回溯和剪枝。

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 即可。

代码实现

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) {
         (n == )  ;
           pow(x, n / );
         n %  ==  ? tmp * tmp : tmp * tmp * x;
    }
}