暑假实习笔试的反思

创建于 访问量:

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

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

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

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

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

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

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

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