Leetcode 50. Pow(x, n) 快速幂

50. 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] 。 

这个题目需要使用快速幂解答：

对于  有：

当 b 为偶数时：

当 b 为奇数时：

由上式递归得以下解法：

  

   

    

     

    
    

     

      class Solution(object):
     
    
   

    

     

    
    

     
    def myPow(self, x, n):
     
    
   

    

     

    
    

     
        """
     
    
   

    

     

    
    

     

       :type x: float
     
    
   

    

     

    
    

     

       :type n: int
     
    
   

    

     

    
    

     

       :rtype: float
     
    
   

    

     

    
    

     

       """
     
    
   

    

     

    
    

     
        if n<0:
     
    
   

    

     

    
    

     

                  x = 1/x
     
    
   

    

     

    
    

     

                  n = -n
     
    
   

    

     

    
    

     
        if n == 0:
     
    
   

    

     

    
    

     
            return 1
     
    
   

    

     

    
    

     
        elif n ==1:
     
    
   

    

     

    
    

     
            return x
     
    
   

    

     

    
    

     
        else:
     
    
   

    

     

    
    

     
            if n % 2 == 0:
     
    
   

    

     

    
    

     
                return self.myPow(x,n/2)**2
     
    
   

    

     

    
    

     
            else:
     
    
   

    

     

    
    

     
                return self.myPow(x,n-1)*x
     
    
  
 

文章来源: blog.csdn.net，作者：沧夜2021，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/CANGYE0504/article/details/89633007