【LeetCode每天一题】Pow(x, n)(平方)

Implement?pow(x,?n),which calculates?x?raised to the power?n?(x，n).

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]

?

思路： 这道题并不难，主要是情况考虑周全，例如 n为负数， x为0，1时等等问题。

　　　使用最简单的方法就是逐个累乘， 但是这种方法会在 n值非常大时，运行时间太长，导致超时。并且效率低。

　　? ?另外一种使用 这样一种公式来解决： aⁿ= a^n/2 + a^n/2 (当n为偶数时)，?aⁿ= （a^n/2?+ a^n/2）a （当n为奇数时），这样计算效率提升。 时间复杂度为O(logn),空间复杂度为O(1)。

 1 class Solution(object):  2  def myPow(self,x,n):  3         """  4         :type x: float
 5         :type n: int
 6         :rtype: float
 7         """  8         if x == 1.0 or x == 0.0: # 特殊情况的判断  9             return x if x == 1.0 else 0.0  
10         neg_flag = False # 指数为负数的标志位 11         if n < 0: 12             neg_flag = True 13             n = abs(n) # 将负指数替换为正整数 14         res = 1
15         while n: 16             if n&1: # 对于指数奇偶数的判断。 17                 res *= x 18             x *= x 　　　　　　　　　　　　 # x = x * x 19             n = n >> 1                          # 指数除以2
20         if neg_flag: 21             return 1/res 22         return res