50. Pow(x, n) - python3

2162 ワード
テキストリンク

50. Pow(x, n)


Implement pow(x, n), which calculates x raised to the power n (i.e. xn).

My Answer 1: Accepted (Runtime: 32 ms - 60.80% / Memory Usage: 14.3 MB - 19.59%)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n > 0:
            return x**n
        else:
            n *= -1
            return (1/x)**n
正xのn次方が戻り,負xの-n次方が戻る
複文で一つ一つ乗じるのが一番遅い.
これも載せたらギリギリ取引されそうな気がしますが….何かルールがあるようです.

Solution 1: Runtime: 32 ms - 60.80% / Memory Usage: 14.3 MB - 53.88%

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # x**n == (1/x)**(-n) 
        # by using the property above we can transform the negetive power problem to positive power problem
        # so that we solve the positive power situation, we also solved the negtive power situation.
        if n < 0:
            x = 1/x
            n = -n
        # We solve the positive power here:
        power = 1
        current_product = x
        while n > 0:
            # if n is odd numberm, we need to time x one more time
            if n%2 : 
                power = power * current_product
            current_product = current_product * current_product
            n = n//2
        return power
  • x^n = (1/x)^(-n)
  • x^(2n) = (x^n) *(x^n)
    • nを2で乗算

    Recursive Solution



    Solution 2: Runtime: 32 ms - 60.80% / Memory Usage: 14.4 MB - 19.59%

    class Solution:
    def myPow(self, x: float, n: int) -> float:

        def function(base = x, exponent = abs(n)):
            if exponent == 0:
                return 1
            elif exponent % 2 == 0:
                return function(base * base, exponent // 2)
            else:
                return base * function(base * base, (exponent - 1) // 2)

        f = function()
        
        return float(f) if n >= 0 else 1/f
    かわいいですね.
    合っているかどうかによって変換して解く.
    [Programmers] 5week
    DFSとBFS-Back Jun(1260,グラフィック)