[50][中等][二分] Pow(x, n)

题目描述

50. Pow(x, n) 剑指 Offer 16. 数值的整数次方

实现 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 位有符号整数，其数值范围是 $[−2^{31}, 2^{31} − 1]$ 。

解题思路

题目的意思是使用最少次数的加减乘除法计算结果. 因此思路是对幂不断的进行二分. 对于偶数幂n, 结果为n // 2幂结果的平方; 对于奇数幂, 结果为n // 2幂结果的平方, 再乘以一个原数x.

递归

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def dfs(exp):
            if exp == 0:
                return 1.0
            odd, half = exp % 2, exp // 2
            y = dfs(half)
            return y * y if not odd else y * y * x
        return dfs(n) if n >= 0 else 1.0 / dfs(-n)