1. 首页

LeetCode 050. 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] 。

难度:Middle

前置知识

  • 递归
  • 位运算

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

解法零 – 遍历法

思路

这道题是让我们实现数学函数,因此直接调用系统内置函数是不被允许的。

符合直觉的做法是将x乘以n次,这种做法的时间复杂度是$O(N)$。

经实际测试,这种做法果然超时了。测试用例通过 291/304,在 0.00001\n2147483647这个测试用例挂掉了。如果是面试,这个解法可以作为一种兜底解法。

代码

语言支持: Python3

Python3 Code:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        res = 1
        for _ in range(n):
            res *= x
        return res

解法一 – 普通递归(超时法)

思路

首先我们要知道:

  • 如果想要求 x ^ 4,那么我们可以求 (x^2)^2
  • 如果是奇数,会有一点不同。 比如 x ^ 5 就等价于 x * (x^2)^2。

当然 x ^ 5 可以等价于 (x ^ 2) ^ 2.5, 但是这不相当于直接调用了幂函数了么。对于整数,我们可以很方便的模拟,但是小数就不方便了。

我们的思路就是:

  • 将 n 地板除 2,我们不妨设结果为 a
  • 那么 myPow(x, n) 就等价于 myPow(x, a) * myPow(x, n - a)

很可惜这种算法也会超时,原因在于重复计算会比较多,你可以试一下缓存一下计算看能不能通过。

如果你搞不清楚有哪些重复计算,建议画图理解一下。

代码

语言支持: Python3

Python3 Code:

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

解法二 – 优化递归

思路

上面的解法每次直接 myPow 都会调用两次自己。我们不从缓存计算角度,而是从减少这种调用的角度来优化。

我们考虑 myPow 只调用一次自身可以么? 没错,是可以的。

我们的思路就是:

  • 如果 n 是偶数,我们将 n 折半,底数变为 x^2
  • 如果 n 是奇数, 我们将 n 减去 1 ,底数不变,得到的结果再乘上底数 x

这样终于可以 AC。

代码

语言支持: Python3

Python3 Code:

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

解法三 – 位运算

思路

我们来从位(bit)的角度来看一下这道题。如果你经常看我的题解和文章的话,可能知道我之前写过几次相关的“从位的角度思考分治法”,比如 LeetCode 458.可怜的小猪

以 x 的 10 次方举例。10 的 2 进制是 1010,然后用 2 进制转 10 进制的方法把它展成 2 的幂次的和。

LeetCode 050. Pow(x, n)

LeetCode 050. Pow(x, n)

因此我们的算法就是:

  • 不断的求解 x 的 2^0 次方,x 的 2^1 次方,x 的 2^2 次方等等。
  • 将 n 转化为二进制表示
  • 将 n 的二进制表示中1的位置pick 出来。比如 n 的第 i 位为 1,那么就将 x^i pick 出来。
  • 将 pick 出来的结果相乘

LeetCode 050. Pow(x, n)

这里有两个问题:

第一个问题是似乎我们需要存储 x^i 以便后续相乘的时候用到。实际上,我们并不需要这么做。我们可以采取一次遍历的方式来完成,具体看代码。

第二个问题是,如果我们从低位到高位计算的时候,我们如何判断最高位置是否为 1?我们需要一个 bitmask 来完成,这种算法我们甚至需要借助一个额外的变量。 然而我们可以 hack 一下,直接从高位到低位进行计算,这个时候我们只需要判断最后一位是否为 1 就可以了,这个就简单了,我们直接和 1 进行一次与运算即可。

代码

语言支持: Python3

Python3 Code:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            return 1 / self.myPow(x, -n)
        res = 1
        while n:
            if n & 1 == 1:
                res *= x
            x *= x
            n >>= 1
        return res

复杂度分析

  • 时间复杂度:$O(logN)$
  • 空间复杂度:$O(1)$

关键点解析

  • 超时分析
  • hashtable
  • 数学分析
  • 位运算
  • 二进制转十进制

相关题目

LeetCode 050. Pow(x, n)
– 原题leetcode链接:https://leetcode-cn.com/problems/powx-n/description/

更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 050. Pow(x, n)

链接:https://www.javascriptc.com/4410.html

« LeetCode 051. N皇后
nginx的listen指令解析你懂了吗»
Flutter 中文教程资源

相关推荐

QR code