leetcode：50. Pow(x, n)

题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，[中等] 50. Pow(x, n) - 图1）。

示例：

  1. 输入：x = 2.00000, n = 10
  2. 输出：1024.00000
  1. 输入：x = 2.10000, n = 3
  2. 输出：9.26100
  1. 输入：x = 2.00000, n = -2
  2. 输出：0.25000
  3. 解释：2-2 = 1/22 = 1/4 = 0.25

解答 & 代码

快速幂（递归分治）：
求[中等] 50. Pow(x, n) - 图2，

  • 如果 n 为偶数，则[中等] 50. Pow(x, n) - 图3
  • 如果 n 为奇数，则[中等] 50. Pow(x, n) - 图4

递归结束条件：n == 1，则直接返回 x

  1. class Solution {
  2. private:
  3.     double calPow(double x, int n)
  4.     {
  5.         // 递归结束条件 1：如果 n == 0，则直接返回 1
  6.         if(n == 0)
  7.             return 1;
  8.         // 递归结束条件 2：如果 n == 1，则直接返回 x
  9.         if(n == 1)
  10.             return x;
  12.         double result = calPow(x, n / 2);
  13.         if(n % 2 == 0)
  14.             return result * result;
  15.         else
  16.             return result * result * x;
  17.     }
  18. public:
  19.     double myPow(double x, int n) {
  20.         // 如果 n < 0，则 x 先转换为 1/x
  21.         if(n < 0)
  22.             x = 1 / x;
  23.         return calPow(x, n);
  24.     }
  25. };

复杂度分析：设求 n 次幂

  • 时间复杂度[中等] 50. Pow(x, n) - 图5：
  • 空间复杂度[中等] 50. Pow(x, n) - 图6：递归深度（栈空间复杂度）

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了 91.49% 的用户