2023年7月30日发(作者：)

leetcode刷题⼼得本⼈以前⼤概搞过半年的算法，不是什么⼤佬，学得也不怎么样，⼀般般。leetcode只刷了200左右（没有⽔题），leetcode简单、中等级别的题⽬⼤部分都可以做。⼤部分公司的笔试题也还⾏，当然了像字节、腾讯那种就太难了，根本顶不住，⾯试遇到的算法题⼀般也能答得上来（其实⾯⼤⼚的机会⽐较少），偶尔也会有失误。先说⼀说刷leetcode的前提，建议不要完全零基础就⼀股脑的去刷题，如果你啥都不会临时突击直接上去刷题的话emmmm，不出意外的话你只会看着别⼈的题解刷题，看了别⼈的思路你也不⼀定会写，就算写出来了很快你就忘了。所以要对常见的算法有⼀定的基础，常见的模型较为了解之后再去刷题。⽐如常见排序（冒泡、快排、插⼊、堆排、归并…）、双指针（快慢指针、左右指针）、贪⼼、⼆分（⼆分查找）、搜索（dfs、bfs、各种剪枝、回溯思想）、动态规划（各种⼦序列、各种⼦串、常见的那⼏个背包问题）、前缀和、树的常见操作（各种遍历、各种树的性质、最⼩⽣成树）、图（最短路、常见性质）、常见数据结构和集合类（链表、队列、栈、map、list、set、并查集都得会⽤），这些基础知识不求你精通，不会写代码都⾏，但是你总得知道这些知识咋回事。当然了如果你是搞过acm竞赛之类的⼤神，这些可以都跳过，直接上⼿。关于怎么学习这些基础的算法知识，个⼈建议新⼿看视频或者看带图的博客，看博客⽂字的话可能看不懂，直接就劝退了，当然有点算法底⼦之后直接看博客也是没问题的。那么该刷leetcode的哪些题，截⽌到⽬前为⽌leetcode已经有1300+的题⽬了，其实不⽤全部都去刷（对⼤部分⼈来说也没那个时间），刷那些⽐较热门的就ok，或者按照各个知识点去刷。所有的题⽬分简单、中等困难三个等级，根据我个⼈的经验来看，简单和中等的题⽬出现的频率是最⾼的，困难级别的很少见，所以建议刷题数量中等>简单>困难。关键是困难的太难了，⼀道题⽬可能两三天你都还搞不出来，⼀来怕把你劝退了，⼆来性价⽐不⾼，所以困难的刷⼀⼩部分就好了。有⼀些很简单没有⽤到任何算法的模拟题、博弈论、最⼤流、特别复杂的树和图操作，⼀般来说这些知识笔试⾯试都不会考。so刷题具体要怎么刷呢，看完题⽬之后不要直接看别⼈的题解，先⾃⼰思考，正常情况下很少会马上就想到最优的解法，要从暴⼒、爆搜开始思考，然后再进⼀步思考怎么去优化复杂度。常见的思考⽅向如下：常见的枚举可以看⼀看枚举的范围是否有序，可以考虑⽤⼆分；双重循环看⼀看是否可以⽤双指针；⼀些要查找的O(n)复杂度的部分是否可以⽤map、set;括号、回⽂之类可以思考⼀下能否⽤栈;⼀些暴⼒搜索的部分看⼀看是否存在根本不可能到达的状态可以考虑剪枝;暴⼒搜索时看看是否有可重复利⽤的状态⽤map或数组把状态存起来（记忆化搜索），然后再看看是否可以⽤动态规划;⼀些枚举的范围很⼤⼀看就知道不可能ac可能思考⼀下是否可以直接推出结论或数学公式（贪⼼的思考⽅向）;⼀些感觉是动态规划的题⽬貌似，貌似每⼀个状态都是有规律的可以尝试⽤打表这种⽐较赖⽪的⽅法;⼀些需要反复计算的部分如果是固定的，可以考虑先计算好然后把它存起来，下次直接拿来⽤（前缀和思想）;⼀些题⽬的条件和经典题型很像的可以考虑直接套⽤经典题型（例如01背包模型，完全背包模型）;⼀些常见的操作可以看看有没有现成的类或⽅法可以直接拿来⽤（例如java⼤数、排序、字符串反转、拼接等常见操作）;⼀些数字的操作可以看看是否涉及到⼆进制，可以尝试下异或、&这些操作;动态规划的题⽬看⼀看这⼀次的状态和上⼀步的状态是否离得很近，如果离得很近可以考虑状态压缩，降低空间复杂度（例如斐波那契，每⼀次的状态只和前⾯两步状态有关）;如果题⽬给出了样例范围可以先通过样例范围反推出算法的时间复杂度，从⽽考虑题⽬⼤概可以⽤什么算法。我的表达能⼒不太好，可能上⾯的描述的思考⽅向有点不太好理解，也是我个⼈的总结，如果有不对的地⽅，请多多指正。顺带说⼀下，leetcode上⾯的题⽬的测试样例并不是特别完善，有⼀些题⽬样例偏⼩，⽤暴⼒做也是可以ac的，所以千万不要因为单纯的ac去刷题，我看到⼀些⽤暴⼒ac了题⽬在评论区炫耀的，还引以为荣喊着ac了就⾏，emmmm⾃⼰体会吧。做完题⽬之后怎么去利⽤题解？很多题⽬是不⽌⼀种最优解的，会存在多种最优解，上⾯已经说过了，不要为了ac去刷题，争取要把多种解法都搞明⽩（尽量看那种热度⾼的、带图的）。看完他们的思路、最优解法之后，要思考最初的暴⼒法是怎么过渡到最优解法的，不要只是单纯的把这道题⽬的最优解法背下来，毫⽆意义。暴⼒法 ----> 最优解法，中间的这个过渡过程才是最重要的，这样学才能体会到学算法的快落，就像学数学⼀样，记住这个公式没有什么⽤，要知道这个公式是怎么从已知条件推出来的，这才是最重要的。最后解答下⼀些常见的疑问。Q:为了笔试⾯试什么时候准备算法⽐较好？A：越早越好，因为算法不同于其他的知识，数据库、语⾔基础这些东西临时突击再不济也能背⼀点下来。可是算法是不能突击的，你早⼀点准备的话，在⾯试⾼峰期的时候就可以把时间放在复习其他知识上⾯了。从笔试情况来看，⼤部分公司基本上都是必考编程题。所以越早准备越好。Q:⽤什么语⾔写算法代码⽐较好？A:习惯了⽤什么语⾔就⽤什么语⾔，语⾔只是⼯具，⽤啥都⾏，不过能⽤c++就尽量⽤c++吧，因为⼤部分题解⽤的都是c++。像java之类的太依赖快捷键了，⼀些笔试不能⽤本地ide，没有快捷键连个包都导不出来，⽽且有⼀些宣讲会是现场笔试的，⼿写代码⾮常影响⼼情和速度，平时有事没事可以多去练练⼿写代码。Q:题⽬读不懂怎么办？A:其实专门针对笔试⾯试的话题⽬读不懂这种情况还是⽐较少的，那些搞竞赛的遇上压轴题题⽬读不懂很正常，笔试⾯试⼀般都是单⼑直⼊。笔试可以结合样例仔细地多读⼏遍题⽬，慢慢的抠字眼，⼀般都能读懂。⾯试的话有时候是⾯试官描述得不太好，可以去问⾯试官，让他说得再详细⼀点，让他多给个样例，让他举个例⼦，然后你再把你的理解和⾯试官说⼀下再次确认。切记题⽬没完全搞明⽩就直接下⼿写代码，这就和开发需求还没搞明⽩就开始code是⼀样的。Q:读完题⽬之后⼀点思路都没有怎么办A:先把最简单最直接的暴⼒做法想出来，然后再慢慢的去优化，参考上⾯的思考⽅向。要知道除了⼤神，很多题⽬都不会让你⼀眼就看到最优的解法，都是慢慢思考出来的，这个从暴⼒法到最优解法的思考过程才是算法的乐趣。就算你想不到最优的解法，能优化⼀点是⼀点，很多公司的判分就是看你能过多少样例。⾯试也是同样的道理，先说出暴⼒法，然后慢慢过渡到最优的解法，体现出这个思考过程，⾯试官会觉得你有思考深度。换句话说，哪怕这题你不会，你把暴⼒法说出来，也总⽐直接放弃跟⾯试官说不会好啊。Q:有思路但是代码写不出来怎么办A:其实对算法⽽⾔，思路才是最重要的，写代码是最后⼀步，也是最简单的⼀步。你可以去问⼀下⾝边搞acm的同学，他会认可这句话的。你要是能把思路说得清清楚楚明明⽩⽩，肯定可以把代码写下来，写不出来是因为平时这类代码写得少，没有去总结。平时要多去看看模板，多去看看⼤神写的代码，像⼆分法是有模板的;链表如果要操作头部通的话常可以给头部加个空节点；⼀些要处理头尾的数组可以从1开始；⼆维数组地图类的题⽬要遍历多个⽅向可以把⽅向存到数组⾥例如int[][] next = {{0,1},{0,-1}…};还有字符串处理、保留n位⼩数、括号类（）的处理、回⽂串等等这些代码都是有模板有技巧的。这样可以让你的代码更加简短容易让⼈读懂，也不容易出错。每⼀次刷题ac完之后都去看看⼤神的代码，平时多练习、多总结、多交流。慢慢的你就可以写出简单⾼效不容易出错的代码了。Q:思路是正确的，但是代码写出来是错的怎么改A:打断点debug，认真查看各个变量的变化，⼀步⼀步往下点，这个过程就是你的算法思路，如果还是看不出来，就拿草稿纸画图，把变量记下来。这个起步是很痛苦的，我刚学dfs的时候调试⼋皇后的代码调了⼀个晚上。Q:思考的时候总是漏掉⼀些情况，代码总是缺⽄少两，不能⼀次ac怎么办A:其实不光是笔试⾯试，搞竞赛的也是⼀样，总是罚时了好多次才能ac。笔试的时候可以马上评测告诉你通过了多少样例还好，如果是不马上告诉你评测结果只让你提交代码的话，本来能ac的只能过80%、50%多难受。建议不管是练习还是笔试，每⼀次提交代码之前都要想出多种特殊样例进⾏多次⾃测，每⼀次都告诉⾃⼰只有⼀次机会，同时也要注意样例范围和格式，如果是⽜客⽹平台笔试的话⼀定要先⾃测再提交代码。怎么想出特殊样例呢？举个简单的例⼦假如让你写⼀个排序算法，可以⾃⼰想出特殊的样例，例如：[],[3],[6,6,6],[3,4,5],[5,4,3],[1,-1,1,-1],[0,0,0],[min,min,min],[max,max,max],这些都算是特殊样例，多去测⼀测，如果代码有问题很快就可以看出来了。最后奉献⼀下⼀位⼤佬的由数据范围反推算法复杂度以及算法内容的总结⼀般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，C++代码中的操作次数控制在 107107 为最佳。下⾯给出在不同数据范围下，代码的时间复杂度和算法该如何选择：n≤30n≤30, 指数级别, dfs+剪枝，状态压缩dpn≤100n≤100 => O(n3)O(n3)，floyd，dpn≤1000n≤1000 => O(n2)O(n2)，O(n2logn)O(n2logn)，dp，⼆分n≤10000n≤10000 => O(n∗n√)O(n∗n)，块状链表n≤100000n≤100000 => O(nlogn)O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平⾯交、⼆分n≤1000000n≤1000000 => O(n)O(n), 以及常数较⼩的 O(nlogn)O(nlogn) 算法 => hash、双指针扫描、kmp、AC⾃动机，常数⽐较⼩的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfan≤10000000n≤10000000 => O(n)O(n)，双指针扫描、kmp、AC⾃动机、线性筛素数n≤109n≤109 => O(n√)O(n)，判断质数n≤1018n≤1018 => O(logn)O(logn)，最⼤公约数