python 数值的整数次方

解决数值的整数次方问题

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
不得使用库函数，同时不需要考虑大数问题。
示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
 

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104

题解

class Solution:
    """
    解题思路: 递归法
    1.如果n为正数，计算x的n次幂分为两种情况:
        1.如果n为偶数,x的n次幂 = x的n//2次幂 * x的n//2次幂  
        2.如果n为奇数,x的n次幂 = x的n//2次幂 * x的n//2次幂 * x
    2.如果n为负数,可以把负数问题转化为正数问题
        1.x的-n次幂 = 1 / x的n次幂
    """
    def myPow(self, x: float, n: int) -> float:
        if n >= 0:
            return self.rPow(x, n)
        else:
            # 因为n的最大区间为2的31次幂 - 1, 所以当计算n的-31次幂时
            # 转换过程出现正数溢出现象，故不能直接使用下面代码
            # return 1 / self.rPow(x, -n)

            # 为了避免正数溢出,则把 x的31次幂 分解为x的30次幂 * x
            return 1 / (self.rPow(x, (-1 * (n + 1))) * x)

    def rPow(self, x, n):
        if n == 0:
            return 1
        if n == 1:
            return x

        # 解决重复计算问题
        half = self.rPow(x, n//2)
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x