2020秋招-刷题

03/21/2020

今天参加了biweek 和 weekly contest.
biweek 的第二题和第四题有些值得注意。第二题时先用的常规思路用一个字典存储，但是报了一个很少碰到的错误: memory limit exceed。time:O(N), space:O(N).  所以针对大量数据的testcase，就要牺牲一些time，转而减少space. 用two pointer 可以让 time: O(nlogn), space:O(1). 面试的时候就要问清楚需求，会不会遇到大量数据。
第四题就是 house robber ii 的变形，在contest 的时候没有反应过来。
至于weekly contest，感觉2，3的medium题目挺难的。反而hard题十分容易AC.... 很奇怪。

03/23/2020

1391M, 1390M, 9E

03/24/2020

lc: 10H, 11M, 12
udacity: lesson4, lesson5 60%

03/25/2020

开始跟着一个刷题列表刷，感觉会更加有计划一些。
今天做完了双指针。167E, 633E, 345E, 680E, 88E, 141E, 524M.
udacity: p1 lesson 5 90% 还剩一点扫尾工作没有做完。

03/26/2020

215M, 347M, 451M
开始进入sort专题了，感觉自己quick sort还不是很熟练。。

03/27/2020

215M, 75M, 455E, 435M, 452M.
今天终于到300了，300/1393，庆祝一下。
现在看lc里面有个30-day leetcoding challenge可以参与下。

03/28/2020

今天把https://github.com/CyC2018/CS-No ... 7%9B%AE%E5%BD%95.md 里面的贪心，二分做完了，分治做了一题，和一起大概有15题。比较有价值的题目就是 241M.
这题用分治的思想按照运算符来进行分治，分别计算出左右两边的可能值，然后进行+-*运算。我一开始的思路是 取三个字符为一个单位，分别计算，用递归做。但是后来想到，万一出现负数怎么办，没法处理负数，就去看discussion了。discussion的高赞也没有解决负数的问题 比如 "-3-1*5" 这里遇到负号了，如果当作运算符就错了。
然后是今天的contest，较以前的比较简单，前三题基本秒了。最后一题想到应该用26进制来做，但是在+1 -1 里面绕了半天没绕出来.... 做到后面就思路紊乱了。

udacity: p1 lesson 6 14%

03/29/2020

今天做完分治，开始“搜索” 这个大章节，现在wfh比较闲，提升一下做题速度，立个flag每天至少5道把。
241M, 95M, 1091M, 279M, 127M.
值得注意的是279M和127M。 这两道用的都是bfs，但是在test 时都出现了 tle.
1. 在279M中，首先是太久没做bfs 忘了用visited 存储导致 tle。 而再加入 visited 后依然出现 tle，原因是循环判断返回的位置。因为我们可以选择在检测到符合要求的结果时，是直接返回，还是先存入queue 中，再取出来再返回。正确的做法应该是直接返回，否则会大大增加时间。
2. 127M， 好题。 这道题比较值得吸收的一个知识点是，在wordList较大时，如何找出只有一个字符不同的两个string。 我之前的做法是，每从queue中pop一个值后，就遍历一次wordList，这样的时间复杂度是O(n^n). discussion中的做法是，把每个word 取 word[:i] + '_' + word[i+1:] 作为key, word 本身作为 value 存入字典中。这样时间复杂度就变成了 O(n^k), k = len(word).
udacity: p1 81% 争取周一把p1做完，最迟不超过周二。

03/30/2020

今天做的是bfs, dfs和backtracking。bfs和dfs掌握都还不错，但是到backtracking就不是特别熟练了，要多加练习。
695M, 200M, 547M, 130M, 417M, 17M, 93M, 79M.
值得重新做的题目： 417M, 79M, 212H(word search I, II).
刚接到个周三晚上的面试，这两天要把udacity的项目放一放了（昨天刚立的flag，秒打脸）

03/31/2020

257M, 46M, 47M, 77M, 39M, 40M, 216M
明天的面试加油啊！