写在前面
今天笔者想来和大家讨论一下,刷算法题的一些心得
说到算法题想必很多同学都会有许许多多的讨论,有的同学认为刷算法题是必修课,有的同学认为算法不实用,工作中用不到。
那么笔者的态度是什么,以前其实已经说过了,还是那句话:必须刷
至于为什么,后面会解释,并且笔者还会和大家讨论如何把题目刷好
实质分析
抛开事实谈逻辑那叫耍流氓,因此笔者就先冒犯一下,把大家当做傻瓜,拿一道题来做个演示,我们在刷题过程中到底在做些什么
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
P A H N
A P L S I I G
Y I R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:
输入:s = "PAYPALISHIRING", numRows = 3
输出:"PAHNAPLSIIGYIR"
示例 2:
输入:s = "PAYPALISHIRING", numRows = 4
输出:"PINALSIGYAHRPI"
解释:
P I N
A L S I G
Y A H R
P I
示例 3:
输入:s = "A", numRows = 1
输出:"A"
提示:
1
第一步:审题
同学们在思考这道题的时候,脑海里是不是会出现以下内容
这道题可以通过模拟Z字形排列的过程来解决。我们可以使用一个二维数组来表示Z字形排列的结果,然后按照从上到下、从左到右的顺序将字符串中的字符填入二维数组中。最后,按照从左到右、从上到下的顺序读取二维数组中的字符,得到最终的结果字符串。
大家看看题目这个东西有半点技术嘛?很明显没有,那么在整个软件工程中,唯一重要,但是文字字里行间不会涉及到技术的东西是啥,没错就是需求,同学们发现没有,大家审题的时候是不是相当于我们在做需求分析。我们到底要具体实现一些什么东西,是不是这个时候都要分析出来
第二步:分析
然后我们接下来刷题的时候会怎么做?是不是同学们脑海中会出现以下内容
- 如果 numRows 为 1,直接返回原字符串 s。
- 创建一个 numRows 行的二维数组,用于存储 Z 字形排列的结果。
- 初始化当前行和当前列为 0,表示当前要填入的位置。
- 遍历字符串 s 中的每个字符:
- 将当前字符填入二维数组的当前位置。
- 如果当前行小于 numRows-1,表示还可以向下移动一行,将当前行加 1。
- 否则,表示已经到达 Z 字形的底部,需要向上移动一行,将当前行减 1,同时当前列加 1。
- 按照从左到右、从上到下的顺序读取二维数组中的字符,得到最终的结果字符串。
时间复杂度分析:遍历字符串 s 的时间复杂度是 O(n),其中 n 是字符串的长度。最后按照从左到右、从上到下的顺序读取二维数组中的字符的时间复杂度也是 O(n)。因此,总的时间复杂度是 O(n)。
空间复杂度分析:创建二维数组的空间复杂度是 O(numRows * n),其中 numRows 是行数,n 是字符串的长度。最后返回的结果字符串的空间复杂度是 O(n)。因此,总的空间复杂度是 O(numRows * n)。
同学们发现服务器托管网没有,我们在敲代码前,需要干什么,对,到底要怎么实现需求,我们脑海中需要有一个大致的步骤,先做什么后做什么,需要很清楚,这像不像软件工程中的设计阶段
第三步:编码
这一步我想是大家最熟悉的阶段,笔者就不再过多阐述了,但是笔者这里还想再次强调一下,包括之前不止一次强调过,敲代码这项工作大约只占整个软件工程中的两到三成,现在我想大家应该又能够有点感受了吧,很多同学为什么觉得敲代码痛苦地不得了,因为同学,你把很多前面应该做的事,全部都省略了,编码阶段负责给你前面的偷懒来擦屁股,你当然会觉得痛苦万分。笔者还是那句话,你只会编码,你不叫工程师,你叫程序员。
编码阶段要做的事情只有一个,就是利用你脑中的编程知识,巧妙地实现你前面的分析和设计,这个阶段要想做好,你要做的事情只有一件,就只是对你在用的代码很熟悉,就可以了
事实上分析和设计都是需要单独练的,很多同学从来没有系统练过,只是一味地敲代码,这样不成体系的混乱学习,那怎么会有明显的长进呢。
第四步:调试
往往做好题目以后,会出现各种各样的问题,除了AC会有很多让我们心态爆炸的结果,最典型的就是以下这些
- CE(Compile Error):编译错误。
- 你的程序存在语法错误(C / C++ 最常见的是缺少分号、缺少括号、使用了中文标点符号或者函数调用错误等等)或者OJ系统不支持的写法(较少见)。
- 此时应当仔细检查代码在本机能否通过编译,改正后再次提交。
- PE(Presentation Error):输出格式错误。
- 你的程序几乎能AC了,但是和标准输出数据有点细微的差距(大小写,空格数量,换行数量之类的)。
- 此时应当仔细观察题目给出的输出样例,确认格式无误(选中数据粘贴到编辑器最为稳妥)。
- WA(Wrong Answer):答案错误。
- 你程序输出的结果有错误,与期望输出不匹配(也有可能是因为缺少了必要的换行和空格)。
- 请检查你的程序是否出现了致命的逻辑错误,当然有的时候是因为手滑。
- TLE(Time Limit Exceed):超出运行时间限制。
- 你的程序可能因为时间效率不高或者出现了死循环,所以未能在规定的时限内运行结束。
- MLE(Memory Limit Exceed):超出运行内存限制。
- 你的程序占用的内存超过了规定值,可能是因为使用了过大的数组,也可能是没有做到内存释放(较少见)
这个时候我们一般看到这样的结果我们就需要干什么?没错,修改代码中的细节,甚至是整个思路错了,要重新设计代码,有时候看测试样例的时候,我们甚至都会骂街,出题人为什么会给出这么奇怪的测试案例
已经工作的同学们,或者是已经从老师口中对工作有些许了解的同学,试着想想看开发人员和测试人员相爱相杀的画面,再看看现在这个画面,是不是很像,没错,我们一步步迈向AC的过程是在干什么,相当于软件工程中的运维测试。
小结
所以,同学们发现了没有,我们在做算法题的时候,一道中等难度的题目,大约十几分钟到半个小时的过程,我们已经进行了一个简易的软件工程过程,这也就解释了为啥很多厂,对应届生的似乎算法占比很高,现在大家应该明白了吧,因为应届生的项目经验比较少,但是他算法题刷得多,一定程度上就弥补了他对整个工程认知不足的问题。至少软件工程,在他的脑海里形成了一个雏形。公司只要稍加培养,很快就能上手干活。
另外也解释了有些同学强调实习,强调项目经验,实际上也是一样的道理,他已经有了足够多的项目经验,从技术到工程流程他都已经比较熟悉,自然不需要算法来弥补他的缺失。
算法本质
肯定有同学要问了,你讲到现在似乎没扯到算法的内容,同学们,不要急。
如果现在没有算法这个概念,只是告诉你刷题,对于比较细心的同学,你们会怎么做?没错,就是把大量的题目放在一起总结规律,把很多类似的问题放到一起总结共同的方法,甚至写出共同的代码来,以后再遇到,就不用直接分析了,而是直接套用你手上已经总结好的东西,从而大幅加快速度。
那么,前辈们是很聪明的,他们已经帮你都总结好了,同学们平时学的算法和数据结构,就是在不断地解决各种问题中总结出来的成果。
所以,同学们现在明白了吗,你学的算法和数据结构,就等同于是站在巨人的肩膀上,省时省力。但是大家还记不记得算法的概念是什么,算法是一种用于解决问题或执行特定任务的有序步骤的描述。所以,这个东西是没有止境的,同学们还要不断地去总结。
切换语言
很多服务器托管网同学可能都在头疼学几门语言的事情,有些同学学了语言没有地方练习,那么笔者的建议是什么,在前面笔者也已经提到了,编码阶段要做的事情只有一个,就是利用你脑中的编程知识,巧妙地实现你前面的分析和设计,这个阶段要想做好,你要做的事情只有一件,就只是对你在用的代码很熟悉,就可以了。
所以,笔者给大家的建议是什么,针对你已经分析过的题目,你换一个语言再试着去实现一遍,当然编码和设计是相辅相成的,不同的语言可能在设计上会略有不同,但是如果都是面向对象的语言,基本上大体不会差到哪里去。
你只要解决,这个设计在你现在的语言中该怎么实现的问题就可以了。
以后的路
如果看到这篇文章的同学已经工作了四五年时间,那么这个时候还要不要刷题呢,笔者的回答是,还得刷,笔者的理由有以下这些
【1】按照上面已经提到了,已经刷过的题目针对切换语言是很重要的,语言流不流行说实话我们说了不算,未来有啥新的语言,我们必须尽快掌握,否则很有可能就被淘汰了
【2】练习重要环节,刷题这件事情,某种程度上也是软件工程,麻雀虽小五脏俱全。公司项目,拿到称心项目的主动权不在我们手上,个人项目,提出好需求的难度也很高,而刷题这些几千几万条需求,不拿来练习实在是太浪费的
附注
那么今天就和大家聊到这里,希望笔者可以给大家带来一些帮助,笔者接下来会更加努力的工作,给大家带来更多的经验分享,希望同学们工作顺利,早日升职加薪、当上总经理、出任CEO、迎娶白富美、走上人生巅峰,想想是不是还有点小激动呢
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 记一次Redis Cluster Pipeline导致的死锁问题
【源创会预告】1024 程序员节(的前两天),相约开源中国办公室,我们一起聊 AI!>>> 作者:vivo 互联网服务器团队- Li Gang 本文介绍了一次排查Dubbo线程池耗尽问题的过程。通过查看Dubbo线程状态、分析Jedis连接池…