AberSheeran
Aber Sheeran
I know nothing except the fact of my ignorance.

暑假实习笔试的反思

起笔自
所属文集: 校园时光
共计 402 个字符
落笔于

报了今年腾讯暑假实习,提前批笔试只做出来三题。第四题本来应该能做出来却没有,值得反思。

第四题大致意思是,给一个数组,求数组中包含所有非零数字最小子串长度。

这一题,我第一反应是利用集合去重。时间复杂度在O(n²)。TimeOut之后,我想到了另一个方法。

假设最短长度为K,那只需要从K=1开始进行试探。想法很好,时间复杂度O(n×m)。但是!内存超限了!当时我不知道为什么,认为是算法问题,就重新思考新的算法。

直到我今天无意中看到滑动窗口算法的变种,发现我的思路是对的。再仔细回想,发现内存超限的重要原因在于生成子串。

我一次性生成了全部长度为k的子串,那么当然超限。其实这在Python里很好解决,只需要一个yield,就可以了。

而我当时偏偏没想到,不该不刷题啊!

立下一个Flag,校招前在LeetCode-Cn刷题满999题。


但是我过了!所以不刷题了,安心接着造轮子。

七月深圳腾讯见!

如果你觉得本文值得,不妨赏杯茶
开发易班的血泪史
没有下一篇