Live 2
Big-O
- Big-O: asymptotic behavior of a function，渐近线逼近描述快慢。
- 非正式定义：忽略lower-order items.
- O(1): 不根据输入值规模变化。
- O(logN):
- O(N^1/2):
- O(N):
- O(NlogN):
- O(2^N): two to the power of N.
切题四件套
- clarification
- possible solutions: compare（时间和空间复杂度）、optimization（加强）。
- coding
- test cases
Live 3
Queue and Stack
先入先出v.s.后入先出
例题
- lc125
- lc20
- lc32
Live 6
DFS
- 题中无图／树，心中有图/树。例如字符串最少多少次变换后到达另一个字符串其实就是最短路径问题。
- 基于状态迁移的一种遍历；为了判重需要二维布尔数组/Set标记是否访问。
- 吞吐使用Stack。
BFS
- 与DFS类似，只是吞吐变成了Queue. 注意在graph中也需要一个visited数组来保证每次都是首次访问。
例题
- merge two sorted lists;
- lc23 merge k sorted lists;
- lc239 sliding window max
- lc480 sliding window median
Live 7
DFS/BFS 例题
- lc22 generate parentheses
- lc515 largest in BT row
- lc102 level traversal
Live 8
Dyanamic Programming
- 递推（从前往后推导，而不能仅仅理解为递归里加个cache）
- 状态的定义（状态实在定义不了的话，就考虑是否可以增加一个维度）
- 最优子结构（实现
getOptimizedState） - 状态转移方程
DP与分治法区别
- 适合于动态规划求解的问题，经分解后的字问题往往不是相互独立的。下一个阶段子问题的求解需要建立在上一阶段解的基础之上。
三大属性
- 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，则该问题具有最优子结构。
- 无后效性：某阶段的状态一旦确定，就不受后续状态/决策的影响，不会出现回溯。
- 有重叠字问题：子问题之间不独立，一个子问题可能在后续阶段决策中被多次用到。
例题
- lc300：状态就是以当前元素为结尾的子序列长度，只要比前面任意一个元素大就可以从该元素转移过来。
- lc64：可以BFS/DFS上下左右搞一波，也可以DP。
Live 9
DP例题
- lc70：有很多follow-up.如果可以走1…k步，就需要不断累加
dp[i - 1]...dp[i - k]。如果限制「上一步走了x，这一步就不能走x」，则需要增加一个维度来保存该处走的是多少步到达的；如果限制「上一步走x、上上步走y，这一步不能走x或y」，就再增加一个维度。 - lc91：DP在字符串处理中经常用到，状态就是当前长度为止有多少种decode方式。
- 股票系列题：