9月刷题/Mock interview接龙活动（缺米刷题的来）

Day 78, solved 1 problem.

4道g家的高频题

打卡一道题 Brute force可以用O(mn)实现 KMP algo把时间复杂度简化为O(m+n)

12/9 打卡

2 Medium, 1 Hard

打卡 1 easy, 2 medium, 1 hard

9/12 day12
152
39
40

爆offer了！！！但是刷题不能停

9.12 打卡第7天

areFollowingPatterns//lc 290. Word Pattern
暴力：map(string, list< Integer >)记录每个string元素都index. 然后for loop 一个string数组，每个字符都去check下map中都index list是否相等，不相等false
优化：直接比。map< strings[i], patterns[i]]>,map2< patterns[i], strings[i]]>. 如果存在key，但当前对应但另一边string不一样，false。
需要2个map。有可能多个对一个。也可能一个对多个
也可用1个map，但是长度变为2倍。map: string, index.
a, 0, b, 0, c, 1, d, 1
存在问题。 a c c vs a d d true;
containsCloseNums //219. Contains Duplicate II P家题，之前有做
暴力：map(value, list index); check list.size()>2 && 差值小于k
优化：题意变为：找相等value下，index差值最小。遍历一遍，不断更新map(value, new index)
涉及index，不能乱用排序。
climbingStaircase //70. Climbing Stairs
backtracking基本题，而且输出顺序也正好是递增
lc 70: 注意count不能放在入参里面。只能是全局变量。因为是值引用。嵌套层的count不会影响最外层
而用res，是地址引用。内部变化，最外层也会变化。backtracking 和 记忆化 只能选一个。

offer offer快来呀
求加米～