关于算法笔试的几个套路，一点就透

博文视点Broadview

发布于 2023-05-19 19:16:08

1810

发布于 2023-05-19 19:16:08

文章被收录于专栏：博文视点Broadview博文视点Broadview

我知道各位是被标题吸引进来的，那就不废话，先说几个算法笔试的硬核套路，再说说语言选择和做题复习的策略。

避实就虚

大家也知道，大部分笔试题目都需要你自己来处理输入数据，然后让程序打印输出。判题的底层原理是，把你程序的输出用 Linux 重定向符 > 写到文件里面，然后比较你的输出和正确答案是否相同。

那么有的问题难点就变得形同虚设，我们可以偷工减料，举个简化的例子，假设题目说给你输入一串用空格分隔的字符，告诉你这代表一个单链表，请你把这个单链表翻转，并且强调，一定要把输入的数字转化成单链表之后再翻转哦！

那你怎么做？真就自己定义一个 ListNode 单链表节点类，然后再写代码把输入转化成一个单链表，然后再用让人头晕的指针操作去老老实实翻转单链表？

搞清楚我们是来 AC 题目的，不是来学习算法思维的。正确的做法是直接把输入存到数组里，然后用双指针技巧几行代码给它翻转了，然后打印出来完事儿。

我就见过不少这种题目，比如题目说输入的是一个单链表，让我分组翻转链表，而且还特别强调要用递归实现，就是我们旧文 K 个一组翻转链表的算法。嗯，如果用数组进行翻转，两分钟就写出来了，嘿嘿。

还有我们前文扁平化嵌套列表讲到的题目，思路很巧妙，但是在笔试中遇到时，输入是一个形如 [1,[4,[6]]] 的字符串，那直接用正则表达式把数字抽出来，就是一个扁平化的列表了……

巧用随机数

再说一个鸡贼的技巧，注意那些输出为「二值」的题目，二值就是类似布尔值，或者 0 和 1 这种组合有限的。

比如说很多题目都类似这样，巴拉巴拉给你说一堆条件，然后问你输入的数据能不能达成这些条件，如果能的话请输出 YES，不能的话输出 NO。

如果你会做当然好，如果不会做怎么办？

首先这样提交一下：

public class Main {    public static void main(String[] args) {        System.out.println("YES");    }}

看下 case 通过率，假设是 60%，那么说明结果为 YES 有 60% 的概率，所以可以这样写代码：

public class Main {    public static void main(String[] args) {        // 60% 的概率输出 YES，40% 的概率输出 NO        System.out.println((new Random().nextInt() % 100) < 60 ? "YES" : "NO");    }}

多提交几次，整出个 80% 以上的 case 通过不是问题。

嘿嘿，labuladong 说了，这题你可以不会，但是一定要在力所能及的范围内做到极致！

概率大师

说一个场景，如果笔试出现那种恶心人的单选，四个选项全都没见过，然后你蒙了一个 C。

假设，过了一会你突然灵光一闪，唤起一些零碎的记忆，确定 B 选项是错的，那么，这时候你该怎么做？

重新在 A 和 D 中间蒙一个啊哥哥！不重新蒙，正确的概率是 1/4，重新蒙，正确的概率是 3/8，白捡的概率都不要么？

是不是觉得不可思议？是不是觉得我在胡扯？

这样，假设一道选择题有 100 个选项，你随便蒙一个，正确率为 1%，错误率为 99%。

假设现在 labuladong 显灵，帮你在剩下的 99 个选项中排除了 98 个错误选项，只剩下一个选项，然后问你，你继续坚持原来的选择，还是换成帮你排除剩下的那个选项？

换啊！换了之后正确概率是 1 - 1% = 99% 啊！

那如果 labuladong 只帮你排除了 90 个错误选项，剩下 9 个选项，那你要不要换成这 9 个选项中的某一个？

换啊！换了之后正确概率是 (1 - 1%) / 9 = 11% 啊！

那回过来看，四个选项，你开始蒙了一个，后来灵光一闪在剩下三个选项中排除了一个错误答案，那你换不换？

换啊！换了之后正确概率是 (1 - 1/4) / 2 = 3/8 啊！

其实这就是典型的「三门问题」。

编程语言的选择

仅从做算法题的角度来说，我个人比较建议使用 Java 作为笔试的编程语言。因为 JetBrain 家的 IntelliJ 实在是太香了，相比其他语言的编辑器，不仅有 psvm 和 sout 这样的命令缩写（你要是还不知道命令缩写，赶紧面壁去），而且可以帮你检查出很多笔误，比如说 while 循环里面忘记递增变量，或者 return 语句错写到循环里这种由于疏忽所导致的问题。

C++ 也还行，但是我觉得没有 Java 好用。我印象中 C++ 连个分割字符串的 split 函数都没有，光这点我就不想用 C++ 了……

还有一点，C++ 代码对时间的限制苛刻，别的语言时间限制 4000ms，C++ 限制 2000ms，我觉得挺吃亏的。怪不得看别人用 C++ 写算法，为了提高速度，都不用标准库的 vector 容器，非要用原始的 int[] 数组，我看着都头疼。

Python 的话我刷题用的比较少，因为我不太喜欢用动态语言，不好调试。不过这个语言的奇技淫巧太多，如果你深谙 Python 的套路，可以在某些时候投机取巧。比如说我们前文写到的表达式求值算法是一个困难级别的算法，但如果用 Python 内置的 exec 函数，直接就能算出答案。

这个在笔试里肯定是很占便宜的，因为之前说了，我们要的是结果，没人在乎你是怎么得到结果的。

解法代码分层

代码分层应该算是一种比较好的习惯，可以增加写代码的速度和降低调试的难度。

简单说就是，不要把所有代码都写在 main 函数里面，我一直使用的套路是，main 函数负责接收数据，加一个 solution 函数负责统一处理数据和输出答案，然后再用诸如 backtrack 这样一个函数处理具体的算法逻辑。

举个例子，比如说一道题，我决定用带备忘录的动态规划求解，代码的大致结构是这样：

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<String, Integer> memo = new HashMap<>();    static int dp(int[][] orders, int start) {        // 具体的算法逻辑    }}

你看这样分层是不是很清楚，每个函数都有自己主要负责的任务，如果哪里出了问题，你也容易 debug。

倒不是说要把代码写得多规范，至于 private 这种约束免了也无妨，变量用拼音命名也 OK，关键是别把代码直接全写到 main 函数里面，真的乱，不出错也罢，一旦出错，估计要花一番功夫调试了，找不到问题乱了阵脚，那是要尽量避免的。