小李飞刀：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/2 n 2的方式。
• 考虑n为偶数和奇数的情况，判断余数后进行计算即可。
• 每次拆解n/2，最后最小的单位应该为x*x。
• 因为每一轮都为前一轮的解的2次方，所以用递归。

总结：

递归还是比较绕的，前提是要找到每一次循环的出口，否则极容易变成死循环。

马上放假了~

统计学+算法+数据结构还是会常伴左右的~

最近还加上了托福的单词，因为受到了单词量统计的刺激，我居然现在知晓的单词量只有3k了，要抓紧背起来了~

自律使我快乐~