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

╰+攻爆jí腚メ 2022-11-06 07:53 74阅读 0赞

### 文章目录 ###

*  面试题16：数值的整数次方
 *   *  解法一：考虑周到拿offer
     *  解法二：快速乘进行局部优化

# 面试题16：数值的整数次方 #

题目描述：

> 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
> 
> 题目链接：[LeetCode][] [牛客网][Link 1]

## 解法一：考虑周到拿offer ##

> 思路：
> 
> 参数 base：
> 
>  *  若是 0
>  *  若是 1
> 
> 参数 exponent：
> 
>  *  若是负数
>  *  若是 0
>  *  若是 1

class Solution { 
    public:
        double Power(double base, int exponent) { 
            if(exponent == 0) return 1.0;
            if(exponent == 1) return base;
            if(base == 0.0) return 0.0;
            unsigned int absEx = (unsigned int)abs(exponent);
            double res = func( base, absEx);
            if(exponent < 0) res = (1.0/res);
            return res;
        }
        double func(double base, unsigned int exponent)
        { 
            double res = 1.0;
            for(unsigned int i = 1; i <= exponent; i++)
                res *= base;
            return res;
        }
    };

## 解法二：快速乘进行局部优化 ##

> 思路：
> 
> 求 a 的 n 次方公式：  
> ![在这里插入图片描述][20210308173638625.png]

class Solution { 
    public:
        double myPow(double base, int exponent) { 
            if(exponent == 0) return 1.0;
            if(exponent == 1) return base;
            if(base == 0.0) return 0.0;
            if(base == 1.0) return 1.0;
            unsigned int absEx = (unsigned int)abs(exponent);
            double res = func( base, absEx);
            if(exponent < 0) res = (1.0/res);
            return res;
        }
        double func(double base, unsigned int e)
        { 
            if(e == 0) return 1;
            if(e == 1) return base;
            double res = func(base, e >> 1);
            res *= res;
            if(e & 0x1 == 1) res *= base;
            return res;
        }
    };

[LeetCode]: https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
[Link 1]: https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
[20210308173638625.png]: /images/20221023/ecd73fb768de49d7b25252ae17b4fbdd.png