【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