2020秋招-刷题

02/16/2020

刷题总数上200啦! 200/1354
78M. Subset,  
90M. Subset II,  
39M Combination Sum,
这三道题都是backtracking的模版题。 backtracking 放在 state space tree 中便是 dfs 解法， 可以理解为一种优化过后的 brute force。对于最后一道 39M. Combination Sum, 普通的dfs传递(list, target,path, result) 然后在recursion函数内进行 for 循环找数字是可以实现的， beats 40%。
但是如果先把 list 排序后，在传递的时候使用 (list, target, index, path, result) 的话，就可以在碰到第一个不满足要求的数字后直接停止。可以省下很多时间,  beats 97% .

zjy1825945 发表于 2020-2-17 13:36
02/16/2020

刷题总数上200啦! 200/1354

加油！！

02/17/2020

40M. 51H, 44H, 213M
今天做的题型已经从 dfs 慢慢变到 dp了， dp 大魔王它终于leile ! 看了挺多地方的思路，感觉最有感触的是：dp解是从 brute force中来的，唯一区别就是dp不用计算它已经算过的东西 (例如斐波那契). 相比之下dfs 更像是 brute force.
但是 dp 中的 top-down dp 和 bottom-up dp 还不是很理解。明天再继续！
（今天尝试做 85H 的时候，思路完全紊乱来，做炸了，以后再试试。。。）

02/18/2020

现在在学习dp。 为了训练看到题目后能够判断出这题是dp 还是dfs，今天开始采取点开两个tag，然后乱序点开几道题然后重新排序，望以此训练解这两个题目的能力。
98M- tree traversal. 这道题在于BST定义的理解，即左边的叶子一定比父节点小，右边的叶子一定比父节点大。*但是同时，叶子结点要满足上一级的限制条件。在访问下一层叶子时，叶子值的范围一定是上一层叶子范围基础上再加上父节点的限制。举个例子，[a,b,c]这样一个subtree。 假设 a 的取值范围是(l,r)， 那么 b的取值范围一定是 (l,r) 和 (-∞, a) 的交集，因此 b 的范围是 (l, min(a,r)). 同理， c 的范围是(max(l,a) , r).
120M-DP. 算是相当简单的一道dp题了. follow up的 space O(n) 还没做，明天继续。
129M-DFS. DFS模版题。

02/19/2020

812E, 316M -- DFS
690E, 96M -- DP
316, 和96 需要重新刷！

02/20/2020

review: 366M-DFS
new : 96M-DP, 95M-DP, 312H-DP
366M 这道题是backtrack的基本运用，用一个字典存储{level: [node]}就好
95M，96M：Unique Binary Search Trees 这两道题真是入门 dp 的好题！运用了分治的思想，这个思想在后面 312m 中也有运用到。95M - Unique BST II 把树的左右两个子树用dictionary 存储为 {(start, end): [TreeNode] }， 这种存储方式以前没有用过，因此第一时间想到的是用 2D matrix 来存储。见过了后以后就有思路了。
312H 这题出的太好了，完美的运用分治的思路。适合以后再次重新刷。

今天刷了一天dp， 感觉对与 bottom-up 和 top-down 的理解又多了一些。目前的认知是，因为dp 是要从 subproblem 一步一步解决到最后的问题。所以应该是运用 bottom-up dp 来解决会比较符合思路。

02/21/2020

8M, 48M, 994E, 286M, 130M
从48m开始写的，一路跟着相似题目继续做下去的，越做越有感觉。加油！

02/22/2020

还在做 1048M, 先来打个卡。今天忘了做contest .... 很亏。
317M, 1162M 两道bfs, 感觉bfs很多都是求小岛距离之类的问题。
138M double linked list

-----  补充 -----
赶着最后几分钟把 1048M 的 dp 作出来了！ 很开心！
虽然题目不是很难， 但是是一眼看出来这道题目要用dp 做，并且基本一遍bug free。

02/23/2020

Leetcode: 225 / 1363,
Udacity, full-stack developer: C2 9%

今天在朋友的推荐下刚开了一个Udacity full-stack developer 的网课，希望能增加一些项目经历，也能够学习一些全栈的知识。也每天记录一下，督促一下自己。
Leetcode 45M, 55H, 1306M, 785M, 261M.
比较有趣的就是785M Is Graph Bipartite? 这个题目是 graph coloring 的题型，之前没有做过所以刚碰到时候一脸懵逼好无头绪。但是感觉面经里面看到挺多，做过一次后也多少有了点感觉。

02/24/2020

47M.
267M.
73M
74M
感觉现在题做的有些感觉了，于是从头开始按序号刷没做过的新题。现在不是hard题，很多可以一遍bug free. 下一阶段提速增加题量吧，每天5道以上。
Udacity 今天基本没学。