# 算法笔试骗分套路
![](https://labuladong.github.io/algo/images/souyisou1.png) **通知:[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.0;[第 13 期刷题打卡](https://mp.weixin.qq.com/s/eUG2OOzY3k_ZTz-CFvtv5Q) 最后一天报名!另外,建议你在我的 [网站](https://labuladong.github.io/algo/) 学习文章,体验更好。** **-----------** 首先回答一个问题,刷力扣题是直接在网页上刷比较好还是在本地 IDE 上刷比较好? 如果是牛客网笔试那种自己处理输入输出的判题形式,一定要在 IDE 上写,这个没啥说的,但**像力扣这种判题形式,我个人偏好直接在网页上刷**,原因有二: **1、方便** 因为力扣有的数据结构是自定的,比如说 `TreeNode`,`ListNode` 这种,在本地你还得把这个类 copy 过去。 而且在 IDE 上没办法测试,写完代码之后还得粘贴到网页上跑测试数据,那还不如直接网页上写呢。 算法又不是工程代码,量都比较小,IDE 的自动补全带来的收益基本可以忽略不计。 **2、实用** 到时候面试的时候,面试官给你出的算法题大都是希望你直接在网页上完成的,最好是边写边讲你的思路。 如果平时练习的时候就习惯没有 IDE 的自动补全,习惯手写代码大脑编译,到时候面试的时候写代码就能更快更从容。 之前我面快手的时候,有个面试官让我 [实现 LRU 算法](https://labuladong.github.io/article/fname.html?fname=LRU算法),我直接把双链表的实现、哈希链表的实现,在网页上全写出来了,而且一次无 bug 跑通,可以看到面试官惊讶的表情😂 我秋招能当 offer 收割机,很大程度上就是因为手写算法这一关超出面试官的预期,其实都是因为之前在网页上刷题练出来的。 当然,实在不想在网页上刷,也可以用我的 vscode 刷题插件或者 JetBrains 刷题插件,插件和我的网站内容都有完美的融合: ![](https://labuladong.github.io/algo/images/others/全家桶.jpg) ### 避实就虚 大家也知道,大部分笔试题目都需要你自己来处理输入数据,然后让程序打印输出。判题的底层原理是,把你程序的输出用 Linux 重定向符 `>` 写到文件里面,然后比较你的输出和正确答案是否相同。 那么有的问题难点就变得形同虚设,我们可以偷工减料,举个简化的例子,假设题目说给你输入一串用空格分隔的字符,告诉你这代表一个单链表,请你把这个单链表翻转,并且强调,一定要把输入的数字转化成单链表之后再翻转哦! 那你怎么做?真就自己定义一个 `ListNode` 单链表节点类,然后再写代码把输入转化成一个单链表,然后再用让人头晕的指针操作去老老实实翻转单链表? 搞清楚我们是来 AC 题目的,不是来学习算法思维的。正确的做法是直接把输入存到数组里,然后用 [双指针技巧](https://labuladong.github.io/article/fname.html?fname=双指针技巧) 几行代码给它翻转了,然后打印出来完事儿。 我就见过不少这种题目,比如题目说输入的是一个单链表,让我分组翻转链表,而且还特别强调要用递归实现,就是我们前文 [K 个一组翻转链表](https://labuladong.github.io/article/fname.html?fname=k个一组反转链表) 的算法。嗯,如果用数组进行翻转,两分钟就写出来了,嘿嘿。 还有我们前文 [扁平化嵌套列表](https://labuladong.github.io/article/fname.html?fname=nestInteger) 讲到的题目,思路很巧妙,但是在笔试中遇到时,输入是一个形如 `[1,[4,[6]]]` 的字符串,那直接用正则表达式把数字抽出来,就是一个扁平化的列表了…… ### 巧用随机数 再说一个鸡贼的技巧,注意那些输出为「二值」的题目,二值就是类似布尔值,或者 0 和 1 这种组合有限的。 比如说很多题目是这样,巴拉巴拉给你说一堆条件,然后问你输入的数据能不能达成这些条件,如果能的话请输出 `YES`,不能的话输出 `NO`。 如果你会做当然好,如果不会做怎么办? 首先这样提交一下: ```java public class Main { public static void main(String[] args) { System.out.println("YES"); } } ``` 看下 case 通过率,假设是 60%,那么说明结果为 `YES` 有 60% 的概率,所以可以这样写代码: ```java public class Main { public static void main(String[] args) { // 60% 的概率输出 YES,40% 的概率输出 NO System.out.println((new Random().nextInt() % 100) < 60 ? "YES" : "NO"); } } ``` 嘿嘿,这题你可以不会,但是一定要在力所能及的范围内做到极致! ### 编程语言的选择 仅从做算法题的角度来说,我个人比较建议使用 Java 作为笔试的编程语言。因为 JetBrain 家的 IntelliJ 实在是太香了,相比其他语言的编辑器,不仅有 `psvm` 和 `sout` 这样的快捷命令(你要是连这都不知道,赶紧面壁去),而且可以帮你检查出很多笔误,比如说 `while` 循环里面忘记递增变量,或者 `return` 语句错写到循环里这种由于疏忽所导致的问题。 C++ 也还行,但是我觉得没有 Java 好用。我印象中 C++ 连个分割字符串的 `split` 函数都没有,光这点我就不想用 C++ 了…… 还有一点,C++ 代码对时间的限制高,别的语言时间限制 4000ms,C++ 限制 2000ms,我觉得挺吃亏的。怪不得看别人用 C++ 写算法,为了提高速度,都不用标准库的 `vector` 容器,非要用原始的 `int[]` 数组,我看着都头疼。 Python 的话我刷题用的比较少,因为我不太喜欢用动态语言,不好调试。不过这个语言的奇技淫巧太多,如果你深谙 Python 的套路,可以在某些时候投机取巧。比如说我们前文写到的 [表达式求值算法](https://labuladong.github.io/article/fname.html?fname=实现计算器) 是一个困难级别的算法,但如果用 Python 内置的 `exec` 函数,直接就能算出答案。 这个在笔试里肯定是很占便宜的,因为之前说了,我们要的是结果,没人在乎你是怎么得到结果的。 ### 解法代码分层 代码分层应该算是一种比较好的习惯,可以增加写代码的速度和降低调试的难度。 简单说就是,不要把所有代码都写在 `main` 函数里面,我一直使用的套路是,`main` 函数负责接收数据,加一个 `solution` 函数负责统一处理数据和输出答案,然后再用诸如 `backtrack` 这样一个函数处理具体的算法逻辑。 举个例子,比如说一道题,我决定用带备忘录的动态规划求解,代码的大致结构是这样: ```java public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 主要负责接收数据 int N = scanner.nextInt(); int[][] orders = new int[N][2]; for (int i = 0; i < N; i++) { orders[i][0] = scanner.nextInt(); orders[i][1] = scanner.nextInt(); } // 委托 solution 进行求解 solution(orders); } static void solution(int[][] orders) { // 排除一些基本的边界情况 if (orders.length == 0) { System.out.println("None"); return; } // 委托 dp 函数执行具体的算法逻辑 int res = dp(orders, 0); // 负责输出结果 System.out.println(res); } // 备忘录 static HashMap