美文网首页
50. Pow(x, n) [python]

50. Pow(x, n) [python]

作者: Chiduru | 来源:发表于2020-01-09 01:07 被阅读0次

    【Description】
    Implement pow(x, n), which calculates x raised to the power n (xn).

    Example 1:

    Input: 2.00000, 10
    Output: 1024.00000
    Example 2:

    Input: 2.10000, 3
    Output: 9.26100
    Example 3:

    Input: 2.00000, -2
    Output: 0.25000
    Explanation: 2-2 = 1/22 = 1/4 = 0.25
    Note:

    -100.0 < x < 100.0
    n is a 32-bit signed integer, within the range [−231, 231 − 1]

    【Idea】
    主要是注意 x和n 在不同取值范围时的计算方式。
    首先考虑特殊值:x=0/ n=1/ n=0/x=1,简化计算;
    之后,n<0时,可以将x做一下倒置;
    最后,如果直接用for i in range(abs(n)) ,时间复杂度过高会报错,这个题的主要考察点也在于简化次方的循环计算次数。O(n)简化直接想O(log(n)) 必然需要二分回溯,就会联想到抽取平方跳步计算了。
    一个tips:
    奇数次方时,取 self.calPow(a*a, (b-1)/2) * a 就可以实现回溯了。

    【Solution】

    class Solution:
        def myPow(self, x: float, n: int) -> float:
            if n == 0:
                return 1
            if x == 1 or n == 1 or x == 0:
                return x
            if n < 0:
                x = 1.0/x
            res = self.calPow(x, abs(n))
            return res
            
        def calPow(self, a, b):
            if b == 1:
                return a
            if b%2 == 0:
                result = self.calPow(a*a, b/2)
            if b%2 == 1:
                result = self.calPow(a*a, (b-1)/2) * a
            return result
    
    

    相关文章

      网友评论

          本文标题:50. Pow(x, n) [python]

          本文链接:https://www.haomeiwen.com/subject/wkveactx.html