马上各种校招要开始了,怎么也得准备一下,之前一直在看看机器学习,NLP方面的东西,收获很多。最近换换脑子,回过头来做做leetcode,感觉还是蛮有意思的。今天刷了个水题,AC不高,然而难度也不高。。不知道为啥。第一次提交用了最最锉的方法,找虐的,很明显超时。于是开始想,第一个想到的就是二分,本来要做n次的计算,现在只要log(n)就可以了,没啥边界,注意n是非正数的情况就可以了:
class Solution:
# @param {float} x
# @param {integer} n
# @return {float}
def myPow(self, x, n):
res = 1
if n == 0:
#return 1
if n < 0:
x = float(1)/x
n = 0-n
while(n > 0):
if n % 2 == 1:
res *= x
n = n/2
x *= x
return res
之后还想过是不是可以弄个3次方、4次方啥的,后来给AC了也就没整了。不过想想道理也是一样的,就是考虑不能整除的情况,相对来说,2次方考虑的较少,时间也算可以。不过上面非递归的情况理解起来有点困难的话,来个递归的版本:
class Solution:
# @param {float} x
# @param {integer} n
# @return {float}
def myPow(self, x, n):
if n < 0:
x = float(1)/x
n = 0-n if n == 0:
return 1
v = self.myPow(x, n/2)
if n % 2 == 0:
return v * v
else:
return v * v * x