LeetCode题解（python）

50. Pow(x, n)

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

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

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解题心得

本题看起来很简单嘛，for循环，一直乘，正数直接结果，负数指数绝对值，结果取倒数。但是，我们怎么会这么写！

要提高效率的话，肯定是折半计算呀~

指数为偶数的时候：折半正好呀，$x \times x$x×x

指数为奇数的时候：折半多1呀，$(x \times x)^{n/2} \times x$(x×x)n/2×x

用递归进行计算~

解题代码

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == -1:
            return 1 / x
        elif n == 1:
            return x
        elif n == 0:
            return 1
        if n%2 == 0:
            return self.myPow(x*x, n//2)
        else:
            return self.myPow(x*x, n//2) * x