- 难度换算: 1道难题 = 2道中等题 = 6道简单题
- 每日目标：做到需要收费的时候每天4题及其以下
- 160题附近开始收费，此时已完成所有基础数据结构（除图外）
- 变量定义域按照C语言使用（更加规范）
- 算法实现需同时保证性能和可读性
- 变量命名规则：
des_XXX: 表示目标值rec_f: 表示递归/迭代函数
- 时间复杂度：需要达到最低
- 空间复杂度：不超过O(n)即可，非必要不降低到O(1)
- 排序算法：需要全部掌握
- 图论：包括线性表和二叉树（都是特殊的图）
- 哈希：需要能够手动实现
- 循环实现
- 递归实现
- 重要概念：递归 == 循环 + 栈
- 递归和循环的空间、时间复杂度一般相同
- 递归本质是通过栈和循环实现
- 线性表
- 字符串（特殊的线性表）
- 树
- 线段树(segment tree)
- 树状数组(Binary Indexed Tree，BIT)
- 图
- 一般动态规划
- 记忆化动态规划
- Memoization(375)
- 记忆化搜索（从后往前看的递归动态规划）
- 动态规划本质：
- 数学归纳法（递推公式）
- f(x) = f(x - 1) + f(x - 2) + ...
if condition_if:
des_arr.append(path[:])
else:
for condition_for:
path.append()
traceback()
path.pop()
| 题号 |
时间复杂度 |
题目 |
完成方法 |
| 300 |
O(nlog(n)) |
Longest Increasing Subsequence |
|
| 162 |
|
|
未证明可行性 |
| 179 |
|
|
内置排序算法，想到但不能排序出来 |
| 334 |
O(n) |
triplet |
两个数组最优置换 |
nums = [2, 1, 3, 4, 1, 2, 3, 4]
def cmp(x, y):
return x - y # -1 理解为每次x取出最小的一个x
nums.sort(key=functools.cmp_to_key(cmp))
print(nums) # [1, 1, 2, 2, 3, 3, 4, 4]
- 关键题目：73, 139, 337(二叉树的动态规划), 392(使用动态规划理解是难点)
| 题目序号 |
题目描述 |
总结 |
| 105 |
需要加深二叉树 先序|中序 遍历特性的理解 |
? |
| 106 |
需要加深二叉树 中序|后序 遍历特性的理解 |
? |
| 130 |
广度优先遍历/二维数组 |
? |
| 307 |
线段树/树状数组 |
? |
| 题目序号 |
知识点 |
序号 |
| 95(3)、96(3)[需要做出98题再来做这两题] |
树的遍历 |
1 |
| 241 |
和 95 一个类型 |
2 |
| 292 |
NIM游戏和博弈论 |
3 |
| 309 |
股票买卖/要冷却 |
4 |
| 310[超时后看答案解出来的,类似找重心的过程] |
减节点/树的直径 |
5 |
| 题目序号 |
题目知识 |
| 204 |
prime |
| 279 |
四平方定理 |
| 372 |
super pow |
- (x * y) % m == ((x % m)*(y % m)) % m
- 该表达式可以分类讨论证明，具有递归累计效果
| 题目序号 |
描述 |
| 205 |
同构字符串 |
| 207 |
图的遍历、环的判定 |
| 227 |
一般表达式求值 |
| 232 |
双栈实现队列&&T(n) = O(1) |
| 238 |
productExceptSelf |
| 241 |
表达式添加括号的不同方法 |
| 274 |
计数排序 |
| 287 |
Floyd 数组重复数字判定/抽屉原理 |
| 292 |
NIM游戏、博弈论 |
| 319 |
灯泡开关(brainteaser) |
| 380 |
Insert Delete GetRandom O(1) |
| 496 |
Next Greater Element I |
| 操作 |
意义 |
| x&(x - 1) |
用来去除 x 的最右边的 1 |
| x&(-x) |
lowbit，也就是取出最低位1代表的数字(也就是最右边的1和后面的0) |