Hike News
Hike News

小李飞刀:leetcode我又来啦~

写在前面

年前嘛,就是各种涣散的状态。

在拖完地板之后,想想还是补上今天的题解吧~

感谢小佳扬推荐的题目,默默的复习了一把递归~

第一题

50. Pow(x, n)
难度:中等
实现 pow(x, n) ,即计算 x 的 n 次幂函数。

我的解题代码:

class Solution:
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if not n:
return 1
if n < 0 :
return 1 / self.myPow(x, -n)
if n % 2:
return x * self.myPow(x, n-1)
return self.myPow(x*x, n/2)

参考了部分评论区的题解。
效率上还是可以的,复杂度在N(logn)左右。

我的解题思路:
一开始的时候小佳扬说是坑,我还在想不就是循环么。
后来她说要考虑怎么降低复杂度,否则会超时,就开始认真的思考了。

  • 因为是n次幂,如果直接循环,复杂度就是O(n)了。
  • n次幂可以拆解为n/2n2的方式。
  • 考虑n为偶数和奇数的情况,判断余数后进行计算即可。
  • 每次拆解n/2,最后最小的单位应该为x*x。
  • 因为每一轮都为前一轮的解的2次方,所以用递归。

总结:
递归还是比较绕的,前提是要找到每一次循环的出口,否则极容易变成死循环。
马上放假了~
统计学+算法+数据结构还是会常伴左右的~
最近还加上了托福的单词,因为受到了单词量统计的刺激,我居然现在知晓的单词量只有3k了,要抓紧背起来了~

自律使我快乐~