写在前面

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

在拖完地板之后，想想还是补上今天的题解吧~感谢小佳扬推荐的题目，默默的复习了一把递归~

第一题

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了，要抓紧背起来了~

自律使我快乐~