LeetCode50：Pow

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

这种题目的关键都是怎么降低时间复杂度。

直接乘是不行的，应该采用幂乘的方法，速度更快。可以采用递归或者迭代，递归消耗更多空间。

 1 class Solution {
 2 public:
 3     double quickMul(double x, long long N) {
 4         double ans = 1.0;
 5         // 贡献的初始值为 x
 6         double x_contribute = x;
 7         // 在对 N 进行二进制拆分的同时计算答案
 8         while (N > 0) {
 9             if (N % 2 == 1) {
10                 // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
11                 ans *= x_contribute;
12             }
13             // 将贡献不断地平方
14             x_contribute *= x_contribute;
15             // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
16             N /= 2;
17         }
18         return ans;
19     }
20 
21     double myPow(double x, int n) {
22         long long N = n;
23         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
24     }
25 };
26 
27 作者：LeetCode-Solution
28 链接：https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/
29 来源：力扣（LeetCode）
30 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。