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值非常大时，运行时间太长，导致超时。并且效率低。
另外一种使用 这样一种公式来解决： an= an/2 + an/2 (当n为偶数时)， an= （an/2 + an/2）a （当n为奇数时），这样计算效率提升。 时间复杂度为O(logn), 空间复杂度为O(1)。
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if x == 1.0 or x == 0.0: # 特殊情况的判断
return x if x == 1.0 else 0.0
neg_flag = False # 指数为负数的标志位
if n < :
neg_flag = True
n = abs(n) # 将负指数替换为正整数
res =
while n:
if n&: # 对于指数奇偶数的判断。
res *= x
x *= x # x = x * x
n = n >> # 指数除以2
if neg_flag:
return /res
return res