1、递归

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

快速幂的思想在于我们在求x的N次幂时，不使用$x\ast x^{N-1}$，而是使用$x^{N/2}\ast x^{N/2}$从而减少递归次数至$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、迭代

我们可以将$x^n$拆成多个$x^{2^k}$项之和，例如$x^{7}7=x^1\ast x^4\ast x^8\ast x^{64}$，而77的二进制表示恰好为$1001101$，其中二进制上每个1的位置表示了有哪些$x^{2^k}$需要相加，我们可以基于这一特点来设计迭代过程。

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);}
};