1、递归

我们最简单的思路就是使用递归，每次就让x乘上Pow(x, n-1)的值。但是这样做的缺点在于递归时间过长会导致超时，因此我们可以使用快速幂进行优化。

快速幂的思想在于我们在求x的N次幂时，不使用x∗xN−1x*x^{N-1}x∗xN−1，而是使用xN/2∗xN/2x^{N/2}*x^{N/2}xN/2∗xN/2从而减少递归次数至O(logN)O(logN)O(logN)。

class Solution {
public:double quickMul(double x, long long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};

2、迭代

我们可以将xnx^nxn拆成多个x2kx^{2^k}x2k项之和，例如x77=x1∗x4∗x8∗x64x^77=x^1*x^4*x^8*x^{64}x77=x1∗x4∗x8∗x64，而77的二进制表示恰好为100110110011011001101，其中二进制上每个1的位置表示了有哪些x2kx^{2^k}x2k需要相加，我们可以基于这一特点来设计迭代过程。

class Solution {
public:double quickMul(double x, long long N) {double ans = 1.0;// 贡献的初始值为 xdouble x_contribute = x;// 在对 N 进行二进制拆分的同时计算答案while (N > 0) {if (N % 2 == 1) {// 如果 N 二进制表示的最低位为 1，那么需要计入贡献ans *= x_contribute;}// 将贡献不断地平方x_contribute *= x_contribute;// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可N /= 2;}return ans;}double myPow(double x, int n) {long long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}
};