【剑指offer】面试题16：数值的整数次方

﹏ヽ暗。殇╰゛Y 2022-06-12 08:23 101阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

## 思路 ##

在代码注释里

## 代码（解法1） ##

不知道为什么我的第一想法就是拿一个数组来保存值…可是完全没有必要，解法1这个代码浪费了没必要的空间。见解法2。

/**
     * 题目：
     * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
     * 
     * 思路：
     * public double Power(double base, int exp)
     * 即 base ^ exp
     * 如果exp为偶数，则拆分成(base ^ (exp/2)) * (base ^ (exp/2))
     * 如果exp为奇数，则拆分成(base ^ (exp/2)) * (base ^ (exp/2)) * base
     * 
     * 注意：exp可能为负数，负数时先将 exp 转换成绝对值，求出答案 res，最终答案为 1/res 
     * 
     * @author peige
     */
    public class _16_Power {
        
    
        public double Power(double base, int exponent) {
            if(base == 0)
                return 0;
            if(exponent == 0)
                return 1;
            boolean positive = exponent > 0;
            exponent = positive ? exponent : -exponent;
    
            double[] power = new double[exponent+1];
            power[0] = 1;
            power[1] = base;
    
            if(positive)
                return Power(base, exponent, power);
            else 
                return 1 / Power(base, exponent, power);
        }
    
        private double Power(double base, int exponent, double[] power) {
            if(power[exponent] != 0) 
                return power[exponent];
            double tmp = Power(base, exponent/2, power);
            if(exponent % 2 == 0)
                power[exponent] = tmp * tmp;
            else
                power[exponent] = tmp * tmp * base;
            return power[exponent];
        }
    
    }

## 解法2 ##

/**
     * 题目：
     * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
     * 
     * 思路：
     * public double Power(double base, int exp)
     * 即 base ^ exp
     * 如果exp为偶数，则拆分成(base ^ (exp/2)) * (base ^ (exp/2))
     * 如果exp为奇数，则拆分成(base ^ (exp/2)) * (base ^ (exp/2)) * base
     * 
     * 注意：exp可能为负数，负数时先将 exp 转换成绝对值，求出答案 res，最终答案为 1/res 
     * 
     * @author peige
     */
    public class _16_Power {
        
    
        public double Power(double base, int exponent) {
            if(base == 0)
                return 0;
            if(exponent == 0)
                return 1;
            boolean positive = exponent > 0;
            exponent = positive ? exponent : -exponent;
    
            if(positive)
                return PowerCore(base, exponent);
            else 
                return 1 / PowerCore(base, exponent);
        }
    
        private double PowerCore(double base, int exponent) {
            if(exponent == 0)
                return 1;
            if(exponent == 1)
                return base;
    
            double tmp = Power(base, exponent / 2);
    
            if(exponent % 2 == 0)
                return tmp * tmp;
            else
                return tmp * tmp * base;
        }
    }

## 解法3（优化到极致） ##

public double Power(double base, int exponent) {
        if(base == 0)
            return 0;
        if(exponent == 0)
            return 1;
        boolean positive = exponent > 0;
        exponent = positive ? exponent : -exponent;
    
        if(positive)
            return PowerCore(base, exponent);
        else 
            return 1 / PowerCore(base, exponent);
    }
    
    private double PowerCore(double base, int exponent) {
        if(exponent == 0)
            return 1;
        if(exponent == 1)
            return base;
    
        //double tmp = Power(base, exponent / 2);
        double tmp = Power(base, exponent >> 1);
    
        //if(exponent % 2 == 0)
        if((exponent & 1) == 0)
            return tmp * tmp;
        else
            return tmp * tmp * base;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    /**
     * 功能测试
     * 1.正数次方
     * 2.负数次方
     */
    private static void test1() {
        _16_Power power = new _16_Power();
        double res = power.Power(1.1, 2);
        MyTest.equal(res, 1.21);
    
        res = power.Power(3, 3);
        MyTest.equal(res, 27);
    
        res = power.Power(-2, 3);
        MyTest.equal(res, -8);
    
        res = power.Power(5, -2);
        MyTest.equal(res, 0.04);
    
        res = power.Power(-2, -3);
        MyTest.equal(res, -0.125);
    }
    
    /**
     * 边界测试
     * 1.base为0
     * 2.exponent为0
     */
    private static void test2() {
        _16_Power power = new _16_Power();
        double res = power.Power(0, 5);
        MyTest.equal(res, 0);
    
        res = power.Power(3, 0);
        MyTest.equal(res, 1);
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews