剑指Offer-数值的整数次方

布满荆棘的人生 2022-02-28 07:06 182阅读 0赞

## 题目描述 ##

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

初步解题思路：用一个循环，循环exponent次做base的累乘。  
进阶解题思路：这题还可以使用**递归**来解决。若exponent为偶数，an=an/2 × an/2；exponent为奇数，an=（a（n-1）/2）×（a（n-1）/2）\*a，这样算法时间复杂度可以降至为O(logn)。  
**最优解：这题最想考的考点就是快速幂解法，快速幂的时间复杂度也为O(logn)。**

> 何为快速幂，举个例子：  
> exponent若为11，11的二进制是1011，11 = 23×1 + 22×0 + 21×1 + 20×1  
> 所以要求base¹¹，则可以转化为求 base2³×base 22¹×base 22º  
> 在每次循环中，使用>>右移判别当前exponent的二进制为1还是0，若为1则乘上相应的倍数，若为0则不变。

## Java初步解题 ##

public class Solution {
        public double Power(double base, int exponent) {
            double  result=1;
            boolean nega = false;
            if(exponent==0 && base != 0)
                return result;
            if(base==0)
                return 0;
            if (exponent<0){
                nega = true;
                exponent = -exponent;
            }
            for(int i=0;i<exponent;i++){
                result*=base;
            }
            if(nega){
                result=1/result;
            }
            return result;
        }
    }

## java进阶解题 ##

public class Solution {
        public static double Power(double base, int exponent) {
            if (exponent == 0 && base != 0)
                return 1;
            if (exponent == 1)
                return base;
            if (base == 0) {
                return 0;
            }
            int n = exponent;
            if (exponent < 0) {
                n = -exponent;
            }
            double result = Power(base, n >> 1);
            result *= result;
            // n>>1，没有0.5，所以还要再乘以一次base，补齐缺失的0.5
            if ((n & 1) == 1)
                result *= base;
            if (exponent < 0)
                result = 1 / result;
            return result;
        }
    }

## 最优解 ##

public class Solution {
        public static double Power(double base, int exponent) {
            if (exponent == 0 && base != 0)
                return 1;
            if (exponent == 1)
                return base;
            if (base == 0) {
                return 0;
            }
            int n = exponent>0?exponent:-exponent;
            double result = 1;
            while(n!=0){
                result = (n&1)!=0? result*base :result;
                base *= base;
                n = n>>1;
            }
            return exponent>0?result:1/result;
        }
    }