打卡群刷题总结0709—— Pow(x, n)

2020-07-14 11:12:43 浏览数 (1)

题目：50. Pow(x, n)

链接：https://leetcode-cn.com/problems/powx-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] 。

解题：

1、依次计算x^(2^0)，x^(2^1)，x^(2^2)，...

然后对n进行分解，转换为一组2的幂的和，将对应的数相乘得到答案。

代码：

代码语言：javascript复制

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1

        # 取得正负符号
        negetive = False
        if n < 0:
            negetive = True
            n = -n

        # 得到下标为2^i对应的数
        times = [0, 1]
        res = [1, x]
        while 2 * times[-1] < n:
            times.append(times[-1] * 2)
            res.append(res[-1] * res[-1])

        # 累积
        result = 1
        index = len(times) - 1
        while n > 0:
            while times[index] > n:
                index -= 1
            result *= res[index]
            n -= times[index]

        if negetive:
            return 1.0 / result
        return result

PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。

PPS：还是得日更呀，总结一下总是好的。

0 人点赞