- 刷题第一遍 5 分钟：读题 + 思考（最多不要超过 15 分钟）,直接看解决：注意！多解法，比较解法优劣（如何 15 分钟后依旧没思路的情况下） 背诵、默写好的解法（这一步很重要）
- 刷题第二遍 将每种解法写一遍（闭卷），反复 Debug，直到代码在 LeetCode 上执行通过,对多种解法之间的优劣进行体会、优化.总结及反思自己写的时候遇到的一些问题
- 刷题第三遍 时隔一天后，再重复做题,对于不同解法的熟练程度进行专项练习
- 刷题第四遍：时隔一周后，反复回来练习相同的题目
- 刷题第五遍：面试前一周进行恢复性训练
| 题目 | 首刷时间 | 最近刷时间 | 毒*n | 复杂度 | 代码片段 |
|---|---|---|---|---|---|
| 前 K 个高频元素 | 2020-06-16 | 2020-07-07 | ✅✅ | heapq.heappush(heap, (-dict[key], key)) | |
| 数对和 | 2020-06-23 | 2020-07-07 | ✅✅ | if dict.get(target-num, 0) == 0 dict[num]+=1 |
|
| 两两交换链表中的节点 | 2020-06-07 | 2020-07-07 | ✅✅ | first_node.next = self.swapPair(second_node.next) | |
| 两数之和 | 2020-06-06 | 2020-07-06 | ✅✅✅ | dict | |
| 旋转数组 | 2020-06-12 | 2020-07-06 | ✅✅✅ | k = k%len(nums) 三段翻转 |
|
| 杨辉三角 II | 2020-06-06 | 2020-07-06 | ✅✅ | 貌似正解是利用动态规划来实现 | |
| 杨辉三角 | 2020-06-06 | 2020-07-06 | ✅✅ | 递归递归 res.append([1]+[res[-1][i-1]+res[-1][i] for i in range(1, numRows-1)]+[1]) |
|
| 反转字符串 | 2020-02-07 | 2020-07-06 | ✅✅✅ | 递归，双指针。要求空间复杂度为O(1)，则只能用双指针实现 | |
| 验证回文串 | 2020-06-20 | 2020-07-07 | ✅✅ | "".join(char.lower() for char in s if char.isalnum()) | |
| 二叉树的前序遍历 | 2020-06-06 | 2020-07-07 | ✅✅ | ||
| 二叉树的中序遍历 | 2020-06-06 | 2020-07-07 | |||
| 二叉树的后序遍历 | 2020-06-06 | 2020-07-06 | ✅✅ | 涉及到打印，所以引入辅助函数helper(root, res) | |
| N叉树的后序遍历 | 2020-06-15 | 2020-07-07 | ✅✅✅ | 时间复杂度：O(n) 空间复杂度：O(n) |
for child in root.children: self.helper(root, res) |
| N叉树的前序遍历 | 2020-06-15 | 2020-07-11 | ✅✅✅✅ | 时间复杂度：O(n) 空间复杂度：O(n) |
class Solution: def preorder(self, root: 'Node') -> List[int]: if not root: return [] res, queue = [], [root] while queue: node = queue.pop() res.append(node.val) for child in node.children[::-1]: queue.append(child) return res |
| N叉树的最大深度 | 2020-06-25 | 2020-07-11 | ✅✅ | 时间复杂度：O(n) 空间复杂度：O(n) |
if not root: return 0 if not root.children: return 1 return max(self.func(node) for node in root.children) + 1 |
| 从中序与后序遍历序列构造二叉树 |
2020-06-10 | 2020-07-10 | ✅✅✅ | 时间复杂度：O(n^2), index() 操作复杂度为O(n),遍历二叉树是O(n) 的。 空间复杂度：O(n)，要存储整棵树 |
if not inorder or not postorder: return None root = TreeNode(postorder[-1]) root_index=inorder.index(postorder[-1]) root.left = self.fun(inorder[:root_index], postorder[:root_index]) root.right = self.fun(inorder[root_index+1:], postorder[root_index:-1]) |
| 从前序与中序遍历序列构造二叉树 | 2020-06-10 | 2020-07-10 | ✅✅✅ | 时间复杂度：O(n^2), index() 操作复杂度为O(n),遍历二叉树是O(n) 的。 空间复杂度：O(n)，要存储整棵树 |
root.left = self.fun(preorder[1:root_index+1], inorder[:root_index]) root.right = self.fun(preorder[root_index+1], inorder[root_index+1:]) |
| 最大二叉树 | 2020-06-15 | 2020-07-07 | ✅✅✅ | python数组边界[ :max_num] [max_num+1: ] | |
| 左叶子之和 | 2020-06-15 | 2020-07-07 | ✅✅✅ | if root.left and not root.left.left and not root.left.right: return root.left.val+self.func(root.right) |
|
| 翻转二叉树 | 2020-06-20 | 2020-07-11 | ✅✅✅✅ | 时间复杂度：O(n) ,每个树节点只访问一次 空间复杂度：O(n)，调用栈n次 |
if not root: return None root.left, root.right = root.right, root.left self.func(root.left) self.func(root.right) return root |
| 对称二叉树 | 2020-06-11 | 2020-07-11 | ✅✅✅✅ | 时间复杂度：O(n) ,每个树节点只访问一次 空间复杂度：O(n)，调用栈n次 |
if not root: return True def recur(left, right): if not left and not right: return True if not left or not right: return False if left.val != right.val: return False return self.recur(left.left, right.right) and self.recur(left.right, right.left) return (root.left, root.right) |
| 路径总和 | 2020-06-07 | 2020-07-07 | ✅✅✅ | if not root: return False sum -= root.val if not root.left and not root.right: return sum == 0 return self.haspath(root.left,sum) or self.haspath(root.right, sum) |
|
| 二叉树的最大深度 | 2020-06-07 | 2020-07-10 | ✅✅✅✅✅ | 时间复杂度：O(n) 空间复杂度：最糟糕的情况下是二叉树不平衡，退化成一个链表，则调用栈的存储为O(n)，最好的情况下，二叉树是平衡二叉树，树的高度是log(N)的，所以此时空复为O(logN) |
|
| 二叉树的最小深度 | 2020-06-16 | 2020-07-11 | ✅✅✅✅✅✅✅ | 时间复杂度：O(n) 空间复杂度：O(n) |
if not root:return 0 if not root.left or not root.right: return self.func(root.left)+self.func(root.right)+1 return min(self.func(root.left), self.func(root.right))+1 |
| 从上到下打印二叉树 II | 2020-06-07 | 2020-07-10 | ✅✅✅ | 时间复杂度：O(n) 空间复杂度：O(n) |
BFS res, queue = [], [root] while queue: tmp = [] for _ in range(len(queue)): node = queue.pop(0) tmp.append(node.val) if node.left: queue.append(node.left) if node.right:queue.append(node.right) 注意：pop() 默认弹出最后一个元素，pop(0)弹出第一个 |
| 二叉树的序列化与反序列化 | 2020-06-23 | 2020-07-11 | ✅✅✅✅ | 时间复杂度：O(n) ,每个树节点只访问一次 空间复杂度：O(n)，调用栈n次 |
def deserialize(self, data): nodes = iter(data.split(',')) def recur(): node = next(nodes) if node == '#':return None else: root = TreeNode(int(node)) root.left = recur() root.right = recur() return root return recur() |
| 交换和 | 2020-07-06 | 2020-07-06 | ✅ | ||
| 分发饼干 | 2020-07-02 | 2020-07-02 | ✅ | ||
| 买卖股票的最佳时机 | 2020-07-03 | 2020-07-04 | ✅✅ | ||
| 验证二叉搜索树 | 2020-06-26 | 2020-07-03 | ✅✅✅✅✅ | ||
| 二叉树的最近公共祖先 | 2020-06-26 | 2020-07-03 | ✅✅✅✅✅✅✅ | 时间：O(n) 空间：O(n) |
if not root or root==p or root == q: return root left = self.func(root.left,p,q) right = self.func(root.right,p,q) if not left:return right if not right: return left |
| 二叉搜索树的最近公共祖先 | 2020-06-20 | 2020-07-11 | ✅✅✅✅ | 时间：O(n) 空间：O(n) |
if p.val > root.val and q.val > root.val elif p.val < root.val and q.val < root.val return root |
| 买卖股票的最佳时机 II | 2020-07-03 | 2020-07-03 | ✅✅ | ||
| 买卖股票的最佳时机 III | 2020-07-03 | 2020-07-03 | ✅✅ | ||
| 最佳买卖股票时机含冷冻期 | 2020-07-04 | 2020-07-10 | ✅✅ | 时间复杂度：prices数组长度为n,所以为O(n)时间复杂度 空间复杂度：如果使用二维数组的话，则为O（n），但是存在优化的空间，就是使用变量代替二维数组，可以优化到O(1) |
dp = [[None, None] for _ in range(n)] dp[0][0] = 0 dp[0][1] = -price[0] dp[1][0] = max() dp[1][1] = max() for i in range(2, n): ............... |
| 买卖股票的最佳时机含手续费 | 2020-07-04 | 2020-07-04 | ✅ | ||
| 买卖股票的最佳时机 IV | 2020-07-04 | 2020-07-04 | ✅ | ||
| x 的平方根 | 2020-07-05 | 2020-07-05 | ✅ | ||
| 有效的完全平方数 | 2020-07-05 | 2020-07-05 | ✅✅ | ||
| 搜索旋转排序数组 | 2020-07-06 | 2020-07-06 | ✅ | ||
| 删除排序数组中的重复项 | 2020-06-10 | 2020-07-07 | ✅✅✅ | if nums[slow] != nums[fast]: slow+=1 nums[slow] = nums[fast] |
|
| 合并两个有序数组 | 2020-06-13 | 2020-07-07 | ✅✅✅ | while num1_index>0 and num2_index>0 num1[:nums2_index+1] = nums2[:nums2_index+1] |
|
| 合并两个有序链表 | 2020-03-02 | 2020-07-08 | ✅✅✅✅ | if not l1: return l2 if not l2: return l1 |
|
| 部分排序 | 2020-07-06 | 2020-07-06 | ✅ | ||
| 最小栈 | 2020-06-06 | 2020-07-07 | ✅✅✅ | if not min_stack or self.min_stack[1] >= x: self.min_stack.apped(x) |
|
| 柱状图中最大的矩形 | 2020-06-08 | 2020-07-08 | ✅✅✅✅ | heights.append(0) stack = [-1] are = 0 for index in range(len(heights)): while heights[index] < heights[stack[-1]] |
|
| 丑数 II | 2020-06-22 | 2020-07-08 | ✅✅✅ | 堆实现和动态规划实现 | |
| 环形链表 | 2020-02-04 | 2020-07-09 | ✅✅✅✅ | 两种情况：存在环和不存在环 不存在环：快指针遍历数组长度n结束，则O(N) 存在环：快指针遍历数组长度n进入环，快慢指针差速长度K，则O(N+K)，K为常数，则O(N) 空间复杂度：只使用了快慢指针，所以O(1) |
if not head or not head.next:return False slow, fast = head, head.next while slow!=fast: if not fast or not fast.next: .......... |
| 环形链表 II | 2020-06-07 | 2020-07-10 | ✅✅✅ | 时间：O(n) 空间：O(n) |
if not head or not head.next:return slow, fast = head, head while True: if not fast or not fast.next: return None slow, fast = slow.next, fast.next.next if slow == fast: break fast = head while slow != fast: ..................... |
| 有效的括号 | 2020-02-04 | 2020-07-10 | ✅✅✅✅ | 时间复杂度：O(n) 空间复杂度：O(n) |
|
| 子集 | 2020-06-25 | 2020-07-11 | ✅✅ | 时间复杂度：O(n2^n) 空间复杂度：O(n2^n) |
def backtrack(index, tmp): res.append(tmp) for i in range(index, n): backtrack(i+1, tmp+[nums[i]]) backtrack(0, []) return res |
| 子集 II | 2020-06-25 | 2020-07-11 | ✅✅ | 时间复杂度：O(n2^n) 空间复杂度：O(n2^n) |