📃 题目描述

题目链接：剑指 Offer 16. 数值的整数次方 (opens new window)

🔔 解题思路

快速幂 + 递归

class Solution {
    public double myPow(double x, int n) {
        // -n 可能会超出 int 的范围 [-2^32, 2^32 - 1] (n = 2^32)
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    private double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }

        double temp = quickMul(x, N / 2);
        return (N % 2 == 0) ? temp * temp : temp * temp * x;
    }
}

• 时间复杂度：O(logn)，即为递归的层数
• 空间复杂度：O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

快速幂 + 迭代 TODO

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：