剑指 Offer 16. 数值的整数次方

    科技2022-07-17  111

    实现函数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; }
    Processed: 0.010, SQL: 8