实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例 1: 输入: 2.00000, 10 输出: 1024.00000 示例 2: 输入: 2.10000, 3 输出: 9.26100 示例 3: 输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25
-100.0 < x < 100.0n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。返回的结果肯定是double类型,base的exponent次方;最后需要判断exponent的正负,如果是负数就返回 1/res;否则返回res。
当exponent是偶数的时候:比如(4,8)表示4的8次方;可以写成(4*4,8/2)即(16,4),所以可以推导出每次将exponent除以2,base*=base,最终到exponent=0为止。
当exponent是奇数的时候:比如(2,7)等于2*(2*2,3)
所以递归写法
public double myPow(double x, int n) { //如果n等于0,直接返回1 if (n == 0) return 1; //如果n小于0,把它改为正数 if (n < 0) return myPow(1 / x, -n); //根据n是奇数还是偶数来做不同的处理 return (n % 2 == 0) ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2); }但是当n=Integer.MIN_VALUE的时候会报错,堆栈溢出,因为Integer.MIN_VALUE的相反数还是本身,这个解决方法就是
if(n<0){ //如果n<0,x的n-1次方乘以(1/x)=x^-n return 1/x*myPow(1/x,-n-1); }非递归
public double myPow(double x, int n) { double res= 1.0; for (int i = n; i != 0; i /= 2 ) { if (i % 2 != 0) { //i是奇数 res*= x; } x *= x; } return n < 0 ? 1.0 / res: res; }