概述
https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
https://leetcode.com/problems/powx-n/
注意为负数的情况哦。
二分法快速求幂（递归法）
要注意，输入范围为整型的范围：-2^31 <= n <= 2^31-1
所以当输入为 -2^31 时，对其取反将导致 int 溢出。
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
bool isNegative = n < 0;
long n2 = n;
if (isNegative) n2 *= -1;
double ans = helper(x, n2);
if (isNegative) ans = 1 / ans;
return ans;
}
double helper(double x, long n) {
if (n == 1) return x;
int rem = n % 2;
n /= 2;
double ans = helper(x, n);
ans *= ans;
if (rem) ans *= x;
return ans;
}
};