剑指Offer系列（java版，详细解析）16.数值的整数次方

题目描述

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

难度中等129

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

测试用例

把 底数 和 指数 分别设为正数、负数和零。

题目考点

• 考察应聘者 思维的全面性。
• 对效率比较高的面试官还会考察应聘者快速做乘方的能力。

解题思路

全面但不够高效的解法

考虑exponent为负数

当指数为负数的时候，我们可以先对指数取绝对值，算出次方的结果之后再取倒数。在想到取倒数的时候，我们又要想到对0取倒数的问题，这就要我们进行错误处理，处理的方式主要有三种：返回值、全局变量和异常。面试的时候可以阐述每种方法的优缺点，然后一起讨论决定选用哪种方法。

值得注意的是，由于0的0次方在数学上是没有意义，因此无论输出是0还是1都可以接受，但这都需要和面试官说清楚，表明我们已经考虑到这个边界值了。

既全面又高效的解法

这是对上面解法的补充，主要利用了下面的公式：

a^n = a^(n/2) * a^(n/2) ; n为偶数
a^n = a^((n-1)/2) * a^((n-1)/2) * a ; n为鸡数

参考解题

全面但不够高效的解法

import java.math.BigDecimal;

/**
 * 数值的整数次方
 *
 */
public class Solution1 {

    private boolean g_invalid_input = false;

    /**
     * 全面但不够高效的解法
     *
     * @param base
     * @param exponent
     * @return
     */
    public double power(double base, int exponent) {
        // 0的0次方没有意义
        if (doubleCompare(base, 0.0) == 0 && exponent == 0) {
            g_invalid_input = false;
            return 0.0;
        }
        int absExponent = Math.abs(exponent);
        double result = powerWithPositiveExponent(base, absExponent);
        if (exponent < 0) {
            result = 1.0/result;
        }
        return result;
    }



    /**
     * 指数为正时，得到的整数次方
     *
     * @param base
     * @param exponent
     * @return
     */
    public double powerWithPositiveExponent(double base, int exponent) {
        double result = 1.0;
        for (int i = 1; i <= exponent; i++) {
            result *= base;
        }
        return result;
    }

    /**
     * 比较两个浮点型大小
     * @param a
     * @param b
     * @return
     */
    public int doubleCompare(double a, double b) {
        BigDecimal data1 = new BigDecimal(a);
        BigDecimal data2 = new BigDecimal(b);
        return data1.compareTo(data2);
    }
}

既全面又高效的解法

class Solution {
    public double myPow(double x, int n) {
        if(x==0)
            return 0;
        long b=n;
        double res = 1.0;
        if(b<0){
            x=1/x;
            b=-b;
        }
        while(b>0){
            if((b&1)==1)
                res*=x;
            x*=x;
            b>>=1;
        }
        return res;
    }
}

补充

返回值、全局变量和异常处理3种错误处理方式的优缺点比较

以后需要用右移运算符代替除以2，用位与运算符代替求余运算符来判断一个数是奇数还是偶数。