如何看待「算法模板」

用户9848496

发布于 2022-09-26 11:21:13

7020

发布于 2022-09-26 11:21:13

文章被收录于专栏：算法不好玩

我学习算法，做算法题以后，经常看到有题解写到「算法模板」，今天就和大家聊一聊什么是算法模板。

以下的观点依然很主观，仅供参考，欢迎讨论。

「算法模板」是编程语言库函数的补充

算法模板是若干个用于算法竞赛的代码片段，这些代码片段是竞赛选手所使用的编程语言库函数的补充。

算法竞赛由机器判题，只看「正确性」和「运行时间」。首先代码得是正确的，然后谁最先做出来，用时最少，谁的名次靠前。所以为了快，因为竞赛用的代码是一次性的，给机器读的，所以很多选手会把变量命名写成 a、b、c，不会写注释，不会注意格式。

为了更快，有一些数据结构，例如「线段树」「树状数组」「并查集」他们不会现场手写，事先准备好，需要的时候复制、粘贴、再改一改 就好了。请注意，绝大多数情况都要修改的哦。即使是我们在「力扣」上做过的问题，除非题目的意思一样，也不会有两道题的代码是一模一样的。

如果不能理解代码每一行的意思，不知道数据结构和算法的应用场景，靠复制、粘贴几乎不可能做对一道问题。

「算法模板」是一个算法和数据结构最简单的样子

算法竞赛和其它数学竞赛、物理化学竞赛不同的是，算法竞赛都是客观题，由机器判题正确与否，所以在线就可以进行。所以就会看到有很多大佬「下凡」，时不时点拨一二，写写题解。

他们写题解的时候就会说「这道题套模板」，这是什么什么的「模板题」。翻译过来就是：这个问题很基础，翻翻书、自己上网查查，要我讲的话就是把书上的东西重新又讲一遍。

所以我们看到的绝大多数被称为「算法模板」的代码片段，都只有代码，而没有题目、没有已知条件和要求的结果。

「算法模板」是个黑话

就跟我们平常会听到的「抓手」「赋能」「优雅」，刷「力扣」的问题会经常听到「AC」「AK」「WA」一样。「算法模板」完整的意思我为大家总结一下：在平常高强度的做题训练中，有一些算法和数据结构经常写，但是自己使用的语言库函数中没有，就需要自己整理一份，只要自己看得懂就行。

「算法模板」有些时候是个噱头

一些培训机构和自媒体宣传的时候会说「公开了自己的算法模板」，因为说「模板」真的很能吸引眼球，其实这些模板指的是：

一些分类好的算法问题；
一些供参考的代码。

吸收了模板的内容成为自己的知识，是有意义的，所以很多时候不用太计较「模板」这个用词，说的人也只是随口一说而已。

真的用的上吗？

我认为绝大多数时候用不上。算法面试和笔试的时候考查的代码量都不大，几乎不会考查很偏门的、需要自己准备提前准备好代码的数据结构和算法。思路和题型有一定范围，按照准备初高中数学题的思路去练习就好。如果你本身有很突出的技能和经验，完全可以和面试官说「不要考我做题」，把我们的优势展示出来，面试是双向选择（这一条大家懂得我意思就好，不展开了，不是建议照做哦）。

算法模板对于我的意义

知道有这么个东西，仅做参考。时至今日，我觉得还能套得上算法模板的地方只有「二分查找」（我做的竞赛题少，现在几乎不做了）。这个模板来自 ACWing 网站（网址：https://www.acwing.com/blog/content/31/），我引用一下：

二分模板一共有两个，分别适用于不同情况。算法思路：假设目标值在闭区间 [l, r] 中，每次将区间长度缩小一半，当 l = r 时，我们就找到了目标值。

版本 1:

当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1，计算 mid 时不需要加 1。

C++ 代码模板：

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本 2：

当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid ，此时为了防止死循环，计算mid 时需要加 1。

C++ 代码模板：

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

这两个模板告诉我：哦，原来所有的「二分查找」都可以写成这样两种形式啊。不过理解这个模板是怎么来的、怎么应用，我进行了一系列的、长时间的猜测、调试和应用。从猜测 while (left < right) 退出循环以后 left 与 right 重合开始，一点一点思考写每一行代码的理由。

我不讲算法模板的原因

因为套不上啊。我自己这关都过不去，我又怎么能和大家分享呢？

我没法告诉读者，该套哪个模板做出来，因为我也不是套模板做出来的。我所有的讲解「二分查找」的问题的重点都花在了「理解题意」「分析单调性」和「如何缩减搜索区间」上，到底二分查找改怎么写，其实写多了慢慢就理解了，加 1 不加 1 也不会是个问题。

现在我做二分查找其实也不是只用这两种写法：

如果要找的目标性质简单，我用 while (left <= right) 这种写法，并且把区间分成三个部分，在循环体中找到，然后程序返回；
而要找的目标性质复杂的时候，我用 while (left < right) 这种写法，并且把区间分成两个部分，把要查找的目标留在退出循环以后。

是不是需要自己整理算法模板呢

如果只是应对算法笔试、面试，整理的代码模板几乎用不上。不过一些在线测评系统，如果不是采用「力扣」这样，给你一个 Solution 类，让我们在里面填充代码的话，那需要几行输入输出的代码，这个可以准备一下，不过这些代码一般都很死板，写几遍都是这个样子。

我认为 一定要自己总结算法思想和相关题型，如果把这样的过程称为整理「算法模板」，我觉得没有问题，因为这样的整理方式有自己的思考，对自己有用。

关于「算法模板」，大家可以参考一下我的算法启蒙老师 liuyubobobo 老师在公众号「是不是很酷」里写的「模板不重要」，我说模板不重要可能没什么分量，大家看看资深竞赛选手是咋说的吧。刘老师的公众号里有很多好玩、有趣的事情，欢迎大家前往阅读。

公众号「是不是很酷」

关于如何学习算法，这里再啰嗦几句：反复做一些经典的问题，然后经常练习。经典问题的分类随便找一个网上的资料都可以，或者就用「力扣」的标签，或者是「力扣」给出的题单，因为题目绝大部分都来自「力扣」。不会有人整理的知识点特别符合每一个人的需求，但是一定要有自己的思考，搞清楚「为什么」更重要。到底需要掌握哪些算法知识点、因人而异。