力扣刷了1500道题的大佬来分享如何准备面试和笔试中的算法题!(干货,建议收藏!)
最近大家都在准备春招和暑期实习,很多即将找工作的朋友都有很多问题,之前的一些推文也帮大家解决了一些疑问。
今天也来分享一个大家最为关心的问题,算法题如何刷?
只要是研发岗位,不管是笔试还是面试,都会考察算法能力,其实也就是编程能力。
很多朋友不知道如何练习或者不知道从何练起,今天给大家分享一下经验吧。(个人建议,仅供参考!)
本人来力扣满打满算也有一年的时间了,目前刷题量大概1500+,竞赛积分2600左右(小白的朋友)。
起初是为了秋招,后来就是每天都会去做一两道题,包括每日一题在内,大概是为了不让自己的脑袋太愚钝。
1 选择一门自己熟悉的语言
大部分同学刷题都是为了面试,那么在自己选定岗位的情况下语言基本上就定下来了,所以刷题时选择自己最熟悉的语言来做题。
第一是可以加深对编程语言的理解,其次是可以熟悉一些常见的API、数据结构、容器、语言特性等。
在面试时很多时候都是白板编程,不像平时写代码有IDE提示或者自动补全,因此熟记常见的API和库函数很重要,凸显基本功扎实。
第二是要熟悉语言自身的一些算法或者API的时空复杂度。
因为算法最关键的两个点就是时间和空间复杂度,所以这个一定要非常熟悉。
因为面试时不仅要写出代码,还需要回答时间和空间复杂度。如果用了某些API,但并没有考虑API自身的复杂度,造成分析错误是非常可惜的。
举个例子:假设在一个循环中调用了某个语言的API去求一个字符串的子串,那么实际上应当把求字串的时间复杂度计算到总的时间复杂度中,而不能直接将其忽略。
2 学会分析时间复杂度
一般的OJ(Online Judge)平台对不同语言的时间要求也不一样。
C/C++ 要求都在 1s
或者2s
Java一般是C++的2倍 Python等语言时间会更宽松
而1s
的时间评测机大概能跑1e7~1e8
左右的数据量,所以会计算时间复杂度对能不能通过题目是一个很好的引导。
时间复杂度对于一个算法来说,有两个至关重要的作用!
决定算法是否会超出时间限制 决定解决该问题会用到什么样的算法
比如我们拿到一道题看到数据范围是
1e5
,那么可以判定这道题的时间复杂度需要控制再O(n)
或者O(nlogn)
因此可判断这道题要么是线性DP,要么是双指针或者是二分等,只要控制在合理的数据范围内,可以排除掉一些不可能的实现方法。
如果对算法掌握不是很好的同学,拿到一道题想到的就是暴力、DFS回溯。
如果数据范围很小,假设只有20以内,那么才可以考虑如此暴力的做法.
举个例子,给
1e5
的数据范围,必然是不可以用DFS回溯或者暴力的方法去做.
数据范围是一个很好的启示,也能避免去写一大堆不可能AC题目的代码,提高刷题、做题以及笔试的效率。
下面给出一张数据范围对应一些可能使用的算法表,根据数据范围去选择对应的算法。
如上图所示
如果 n
小于30的情况下,可以考虑暴力搜索加剪枝;n
如果为100的话一般可以考虑三层循环的区间DP等O(n^3)的做法;n
如果为1000,可以考虑双重循环的DP或者O(n^2logn)的做法
其他的类似上面的图中介绍,不再赘述,根据数据量来选择算法可以更快突破解题思维,这些都是一些常见的刷题常识。(切勿拿到题目就去暴力,那样只会让自己的思维越来越钝化)
比如当我们遇到一道题:
求5e6(5000000)范围内的所有素数
思考:大部分情况下我们想到的方法就是遍历1~1e6的所有数字,然后通过逐个元素判断,这样写出的代码可能如下:
public class Main {
public static void main(String[] args) {
int i = 2;
while (i < 5000000) {
boolean flag = true;
for (int j = 2; j * j < i; j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
System.out.println(i);
}
i++;
}
}
}
//运行时间:超时
上面的代码显然会超出时间限制,但是可以采用更快的方式去找到素数,采用的算法就是素数筛法。详情见204. 计数质数
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int n = (int)5e6;
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
// 从 2 开始枚举到 sqrt(n)。
for (int i = 2; i * i < n; i++) {
// 如果当前是素数
if (isPrim[i]) {
// 就把从 i*i 开始,i 的所有倍数都设置为 false。
for (int j = i * i; j < n; j+=i) {
isPrim[j] = false;
}
}
}
int cnt = 0;
for (int i = 2; i < n; i++) {
if (isPrim[i]) {
System.out.println(i);
}
}
}
}
//运行时间:1467ms
通过上面的两段代码可以得出的结论就是
当看到数据范围比较大的时,一定要选择正确的算法求解,因此也就突出了时间复杂度的重要性。
3 如何去刷题
如果是短期内为了刷题突击面试找工作,可以以重点为主,例如力扣的剑指offer
和HOT100
,高频的经典面试题都会以这两个专题为主。
其次是如果确定要面某个公司的话,可以看看对应的公司的题库,然后按照出现的频率排序,选择较高的一些题目刷。
下面分别是力扣和牛客的公司面试高频题。
其中力扣的需要会员,大家可以用积分兑换,牛客是免费的。
如果是长期性刷题,有好几个月的时间准备的情况下,可以按照专题
来刷,也就是力扣给的tag
,如下图所示。
每个tag
可以按照2简单,3中等,1困难来练习,然后定期再去随机一些题目来强化训练。
如果拿到一道题十分钟左右完全没有思路的情况下,就可以去看题解或者评论区,不用死磕!
学习别人的题解也是一种学习,看完思路记得自己复现一遍,在写的过程中如果再碰到问题再去看题解,切勿直接照抄题解。
如果学有余力并且对自己的要求比较高的话,可以去打一打力扣的周赛。
力扣周赛的题目有时候出的还是很不错的,而且题目比较新,可以得到一些提升,并且能和几千人一起同台竞技的感觉也是很棒的。
竞赛成绩如果能达到Knight说明基础还是不错的,面试的话应该不会出现太多被卡的情况,Knight分数大概是1857左右。
在刷题的过程中,很多题目用到了类似的算法,可以多做整理,整理一些模板。
比如图论
中的最短路问题,回溯
问题等等,很多tag
都可以做总结,然后放在一起对比。
如果有精力去写题解记录自己的刷题心得进步会更加快
刷题不能只求AC,更多的时候是多记录多思考多复习,做到举一反三的效果,哪个专题比较欠缺,就多努力去刷某个专题的题目。
4 如何准备笔试
现在大厂笔试都比较难,门槛也在变高,所以笔试的难度也越来越大。
很多题目都是一些竞赛题或者改编题,因此如果想要笔试不罚坐,仅仅依靠力扣是不够的。
还应该去其他的平台上多提升提升自己
例如洛谷、POJ、codeforces等比较知名的平台
想要提升自己可以在刷力扣之余,多去这些平台上长长见识,多学点总归是有好处的,想要系统的学习或者刷更进阶的题目可以参考 kuangbin专题
网站:https://vjudge.net/article/371
5 总结
总之算法是一个需要长久刷题的过程,短期内突击一般是很难的。
一定要坚持刷题,保持感觉!
这篇文章希望大家可以多多帮忙转发给周围的未来准备找工作或者即将参加秋招的同学或者朋友。
关注小白,让你少走弯路!
推荐阅读