JZ-12 数值的整数次方
数值的整数次方
https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
- 第一种思路，用递归的方式解决：害怕爆栈但还是通过了
public class Solution { public double Power(double base, int exponent) { if(base!=0 && exponent == 0){ return 1.0; }else if(base==0 && exponent!=0){ return 0.0; }else if(exponent>0){ return base*Power(base, exponent-1); }else{ return 1/(Power(base,-exponent)); } } }
- 第二种思路，使用快速幂的方法，时间复杂度：O(logn)，因为n的二进制位个数为logn，空间复杂度：O(1)
public class Solution { public double Power(double base, int exponent) { if(base!=0 && exponent == 0){ return 1.0; }else if(base==0 && exponent!=0){ return 0.0; }else if(exponent>0){ double ans = 1; while (exponent!=0){ if ((exponent&1) == 1){ ans = ans*base; } base = base*base; exponent >>= 1; } return ans; }else{ return 1/(Power(base,-exponent)); } } }
