题目来源
https://leetcode.com/problems/powx-n/
Implement pow(x, n).
题意分析
Input: x,n
Output:pow(x,n)
Conditions:满足一定的内存需求，算法复杂度低一些
题目思路
刚开始以为直接乘就好了，但是爆内存了，仔细看发现其实可以通过二分法利用每次乘的信息，注意到n可以为负数，所以预处理为正数先
- 预处理为正数
- 调用函数：初始化递归条件；二分；针对n为偶数和奇数返回相应值
- 根据预处理返回正确的值（如果是负数就要用1去除）
AC代码（Python）
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
def p(x, n): if n ==0:
return 1.0
half = self.myPow(x, n / 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
s = False
if n < 0:
n = -n
s = True
if s == True:
return (1.0) / p(x, n)
else:
return p(x, n)