（更新offer）胡子大叔刷题直播

直播呢？在哪？斗鱼还是bilibili?

dp最简单，我好菜啊

zkc 发表于 2018-11-9 08:34
直播呢？在哪？斗鱼还是bilibili?

就在本帖啊

今天oncall，回来得晚了。九点多才开始做题。就做了一道hard，Maximum Sum of 3 Non-Overlapping Intervals

粗看之下，没有头绪。如果意识到3是个常数，就没有一开始看上去那么无处着手。这道题的解法有点像两重DP
第一重，是把sum(nums[i:i + k])，以i为起始的这k个数的和存在一个数组里KS里
第二重，是把KS[:i + 1]的数值最大的那个index存在一个数组left里。KS[i:]的数值最大的那个index存在一个数组right里

然后三指针就变成了一指针。

整个思路有点新鲜。但是如果不是3分，而是一个变量n分，做法还是没法推广。有点Best Time to Buy and Sell Stock III的那个意思

刷了Minimum Window Subsequence，个人感觉这和Best Time to Buy and Sell Stock IV都属于DP里最难的题了。（IV可能更难，因为DP的定义非常不清楚

就这道题来说，naive DP还是好懂的，two pointers反向查找可以算一阶进化，pre-compute一下，遇到T[:i+1]然后再找下一个T[:i]，这样DP应该是最优化的了。

新题，hard，花了好多时间。最后Python beat 100%。

然后就Explore-Facebook下面的DP也刷完了，吁——

长舒一口气，这几天DP真的做吐了，下面就刷backtracking吧。这是我印象中比较难的，尤其regex, wildcard啥的。正好上几道DP也都是string match，比较有心理准备

然后果然就做了Regular Expression Matching，因为是印象中比较难的题，之前十月份拖了一个月都没动，现在马上要面试了，吓得拖延症都没了。

其实做了之后发现没有记忆中那么难，比较intuive的递归法能pass oj但是时间太长，最后还是回归到了dp（不是说了不做dp的嘛！

同时感叹下hard的题真的很费时间，做着做着可能就……睡着了。还好早上五点就醒了，玩了会儿继续刷。今天是一个周六，还这么早起，希望也能刷个十道吧，奋斗！

好厉害，这些题我做起来非常吃力

wangyxwyx 发表于 2018-11-11 01:11
好厉害，这些题我做起来非常吃力

hard的我也觉得费劲啊。但是一想到如果面试当场遇到了抓瞎，还不如现在费点时间琢磨清楚好