题解 | #数值的整数次方#

数值的整数次方

http://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00

方法一：暴力求解

判断exponent是否为负数，若为负数则取反且base取倒数进行遍历求解

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param base double浮点型 
# @param exponent int整型 
# @return double浮点型
#
class Solution:
    def to_power(self, a, n):
        if n == 0:
            return 1.0
        if a == 0:
            return 0.0
        res = 1.0
        for i in range(n):
            res *= a
        return res
    def Power(self , base: float, exponent: int) -> float:
        # write code here
        if exponent < 0:
            base = 1 / base
            exponent = -exponent
        res = self.to_power(base, exponent)
        return res

方法二：递归求解（二分）

判断exponent是否为负数，若为负数则取反且base取倒数进行对半求解但是exponent要判断奇偶性若为偶数则直接 a^n = a^(2/n) * a^(2/n) 奇数为 a^n = a^(2/n) * a^(2/n) * a^1 求平方时a * a 比 a ** 2 的效率高

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param base double浮点型 
# @param exponent int整型 
# @return double浮点型
#
class Solution:
    def Power(self , base: float, exponent: int) -> float:
        # write code here
        # 判断exponent是否为负数，若为负数则 取反 且base取倒数 进行对半求解 但是exponent要判断奇偶性
        # 若为偶数 则直接 a^n = a^(2/n) * a^(2/n) 奇数为 a^n = a^(2/n) * a^(2/n) * a^1
        if exponent == 0:
            return 1.0
        if base == 0:
            return 0.0
        if exponent < 0:
            base = 1 / base
            exponent = -exponent 
        res = self.Power(base, exponent // 2)
        if (exponent & 1) == 1:
            res = res * res * base  # a * a 比 a**2的效率高
        else:
            res = res * res
        return res

方法三：

位运算快速求幂

算法流程： 1.当base=0 返回0；当exponent=0时返回1

2.当exponent < 0 时取反且base取倒数

3.初始化res=1

4.循环计算当 exponent = 0 时跳出循环：

	当 exponent & 1 = 1时（为奇数） 当前res *= base 

	exponent 为偶数时， 计算 base *= base

	exponent 右移1位

5. 返回 res

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param base double浮点型 
# @param exponent int整型 
# @return double浮点型
#
class Solution:
    def Power(self , base: float, exponent: int) -> float:
        # write code here
        # 位运算
        if exponent == 0:
            return 1.0
        if base == 0:
            return 0.0
        if exponent < 0:
            base = 1 / base
            exponent = -exponent
        res = 1
        while exponent:
            if exponent & 1: # 判断是否为奇数
                res *= base
            base *= base
            exponent >>= 1  # 位运算
        return res

参考大佬：

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/