JZ12_数值的整数次方.md

JZ12_数值的整数次方

方法一：暴力法遍历一遍求出base的ex次幂的结果返回（注意特殊处理base为0或者exp为0的情况，以及如果次数是负数则注意最后要转为倒数，至于输出保留5位小数不是本接口需要考虑的）

public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0) return 0;
        if (exponent == 0) return 1;
        int flag = 0;
        if (exponent < 0) {
            flag = 1;
            exponent *= -1;
        }
        double ans = 1;
        //暴力循环exp次即可
        for (int i = 1; i <= exponent; i++) {
            ans *= base;
        }
        if (flag == 0) return ans;
        else return 1.0 / ans;
    }
}

方法二：快速幂的迭代形式

快速幂的思想为将低阶的幂运算用高阶的幂运算去代替：3^10 = (33)^5 = 9^5 = 9 * (99)^2 = 9 * 81^2，核心思想是如果能被2除就base做平方运算，如果不行就单乘一个base，剩下继续被2整除~至于除2运算与判断是否为偶数可以用位运算代替

public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0) return 0;
        if (exponent == 0) return 1;
        int flag = 0;
        if (exponent < 0) {
            flag = 1;
            exponent *= -1;
        }
        double ans = 1;
        //快速幂：迭代形式
        while (exponent > 0) {
            //如果为偶次幂则底数平方，指数除2
            if ((exponent & 1) == 0) {
                exponent >>= 1;
                base *= base;
            } else {//如果为奇数则ans乘上当前底数base，指数减1，这样指数在下一轮指数就是偶数了
                exponent--;
                ans *= base;
            }
        }
        if (flag == 0) return ans;
        else return 1.0 / ans;
    }
}

方法三：快速幂的递归形式

递归与迭代有些区别，迭代的过程中base遇到偶次幂平方，遇到奇次幂则ans乘上base，base是逐渐翻倍变大的过程，是比较好理解的，而递归的方式它是倒过来思考：n为偶数时：x ^ n = [ x ^ (n / 2) ] ^ 2，n为奇数时： x ^ n = [ x ^ (n / 2) ] ^ 2 * x，这样假设x ^ (n / 2) 已经求得就能直接求出x ^ n，同理分解为更小的部分

public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0) return 0;
        if (exponent == 0) return 1;
        int flag = 0;
        if (exponent < 0) {
            flag = 1;
            exponent *= -1;
        }
        //快速幂：递归形式（倒过来思考，比较抽象）
        double ans = Pow(base, exponent);
        if (flag == 0) return ans;
        else return 1.0 / ans;
    }

    public double Pow(double base, int exp) {
        //分解到0次幂就返回1
        if (exp == 0) return 1;
        double base2 = Pow(base, exp/2);
        //奇数
        if ((exp & 1) == 1)
            return base2 * base2 * base;
        //偶数
        else
            return base2 * base2;
    }
}