2020秋招-刷题

03/11/2020

4H, 5M, 409E, 266E
开始palindromic 相关训练。
udacity: p1 - 55%

03/12/2020

5M, 7E, 516E.
做palindromic的题目感觉很多都是用dp做的。明天把思路再巩固一下

03/13/2020

review: 5M
new: 336H, 214H, 541E
palindrome的题基本上都是hard题，太艰难了

03/14/2020

今天contest 前三题都做出来了，算是有进步。
最后一题我想的是用一个min heap 存储speed, 然后对efficiency进行排序，取前x 个 index 然后求sum。 time complexity 应该是 O(N lgN), 但是 TLE了。明天起来看看正确做法。

03/15/2020

1383H, 871H, 857H
这三道都是heap的题目。昨天contest最后一题我用heap 的思路是对的，只不过在代码for loop 里面加了一个sum() 导致时间复杂度变成 N**2 了 lol.
今天跟着YouTube 把heap 的基本知识先复习了一下，回忆起了之前算法课上讲的heap的时间复杂度。heapify 和 create heap 的time 一个是 n, 一个是 n*lgn，这个要注意。
然后从昨晚contest的最后一题出发 做了几道关联题。特别是871题，一开始没有想到如何应用heap, 用的brute force解决，时间复杂度到了 n**n。看了李哥的答案，用dp - n**2 和heap - n lgn 各做了一遍，觉得一题多解的思路还是挺关键的，加入复习计划表了。

03/16/2020

23H, 264M, 313M, 263E, 1201M
今天被ugly number ugly了一天，丑哭了。大概总结一下 ugly number II 比价方便的办法是用 3 pointers - time: o(n), 但是我还是比较喜欢用heap 实现，time: O(n lgn)，但是代码看起来比较elegant。同样的对于 super ugly number, 用的dp 的方法思路和 ugly number II 是一样的，time: O(nk)m, 用heap 也可以实现，time: O(nk*lg(nk))

03/17/2020

200M, 694M, 1192H

03/18/2020
今天发烧了.... 头疼了一整天，做不进题目。希望只是着凉不是新冠吧......

03/19/2020

今天身体状况有所好转... 继续来打个卡
7E, 8M, 9M

03/20/2020

11M, 15M, 16M