Leetcode

Leetcode

一些比较好用的函数（Python）

1
2
3
4
5
6
7
8
9


str.split('/')

'/'.join(list)

dict = {}
dict.get(key, defaultvalue)  # 如果key不存在，返回defaultvalue(如果不指定，默认是None)，避免了keyerror

nums = [1,2,3,4]
sum = reduce(lambda x, y: x+y, nums)

数组

双指针：

当一个有序数组需要对两个元素进行枚举的时候，如果随着一个元素的增加，另一个元素会减小，那么可以使用双指针，当第一个指针往右走一个时，另一个往左走若干个。

时间复杂度由O(n^2)降低到O(n)

链表

快慢指针

可以用来寻找中间元素或者判断是否有环
寻找倒数第k个元素：

先让一个指针往后走k个，然后另一个指针从头开始，两个指针一起往后走

动态规划

如果递归的参数只有一个数字之类的，可以考虑使用动态规划将其变为一个数组或者字典，避免一次次的重复调用

Q96

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0]*(n+1)
        G[0], G[1] = 1, 1
        # 将长度结果存储起来，避免重复计算

        for i in range(2, n+1):
            # i 代表长度
            for j in range(1, i+1):
                # j代表选择的节点
                G[i] += G[j-1] * G[i-j]

        return G[n]

搜索

岛屿问题（DFS）

https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/