问题描述
https://leetcode.com/problems/powx-n/
解决思路
采用了二分的思路。举例而言，2^8变成4^4，变成16^2变成256.
问题解惑
- 为什么负数这样处理？ 因为负数最小值-2^32无法由正数最大值2^32-1直接表示，所以先把负数加1，取反，再在最后幂运算结束之后，乘以一个底数，再取倒数。
代码
class Solution {
public double myPow(double x, int n) {
//corner case
if(x == 1 || n == 0) return 1;
if(n == 1) return x;
//the max of integer could not represent the min, so when n < 0 should be processed this way
if(n < 0) return 1 / (x * myPow(x, -(n + 1)));
double res = 1;
while(n > 1){
if(n % 2 == 1){
res *= n;
}
n *= n;
x /= 2;
}
res *= n;
return res;
}
}
复杂度分析
- 时间复杂度：
- 空间复杂度：
