我学习算法,做算法题以后,经常看到有题解写到「算法模板」,今天就和大家聊一聊什么是算法模板。
以下的观点依然很主观,仅供参考,欢迎讨论。
算法模板是若干个用于算法竞赛的代码片段,这些代码片段是竞赛选手所使用的编程语言库函数的补充。
算法竞赛由机器判题,只看「正确性」和「运行时间」。首先代码得是正确的,然后谁最先做出来,用时最少,谁的名次靠前。所以为了快,因为竞赛用的代码是一次性的,给机器读的,所以很多选手会把变量命名写成 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 老师在公众号「是不是很酷」里写的「模板不重要」,我说模板不重要可能没什么分量,大家看看资深竞赛选手是咋说的吧。刘老师的公众号里有很多好玩、有趣的事情,欢迎大家前往阅读。
公众号「是不是很酷」
关于如何学习算法,这里再啰嗦几句:反复做一些经典的问题,然后经常练习。经典问题的分类随便找一个网上的资料都可以,或者就用「力扣」的标签,或者是「力扣」给出的题单,因为题目绝大部分都来自「力扣」。不会有人整理的知识点特别符合每一个人的需求,但是一定要有自己的思考,搞清楚「为什么」更重要。到底需要掌握哪些算法知识点、因人而异。
「力扣」精选题单
这就是今天的分享,感谢大家的收看!