数据结构与算法(Java版) | 几个经典的算法面试题(上)
大家好啊,我是你们的李阿昀,好久不见了,甚是想念大家!这不,从今儿个开始,我又要给大家开个坑了,从本文的标题大家就能看出来,这次我要给大家讲的就是数据结构与算法(Java版),而且我还特地汇总成了一套系列教程,我有理由相信,本套讲述有关数据结构与算法的教程将有可能会是东半球最系统全面的一套教程,所含文章至少不会少于200篇,如若不信,则就请大家拭目以待吧!
关于本套系列教程,有三点我需要向大家说明一下,第一点就是本套系列教程主要讲解的是有关数据结构与算法方面的内容,而且还是基于Java语言来进行讲解的,这一点相信我不说,大家也应该都知道了。之所以要向大家说清楚这一点,是因为在大学里面数据结构与算法这门课大多是采用C/C++语言来讲的,想必大家对此应该都有所体会,而本套系列教程则不同,它采用的是目前最流行的编程语言之一,即我们都熟悉的Java语言,这便是我要向大家说明的第一点。
至于第二点嘛,就是在讲解过程中,我会以图解的形式来帮助大家更好地理解数据结构与算法。
最后,还有第三点,就是我在向大家讲解数据结构与算法这门课时,不可避免地会用到很多资料,例如Google算法编程大赛里面的一些题,有:
- 磁盘问题
- 公交车
- 画图
- ······
另外,就是一些数据结构的经典应用案例了,例如:
- 银行排队叫号(队列)
- 汉诺塔
- 迷宫案例
- 坦克游戏
- 小球找家
- 丢手帕问题
- ······
以上这些题或者应用案例,等需要用到的时候,我再来给大家一一进行介绍啊!
为了勾起大家对数据结构与算法这门课学习的一个兴趣和欲望,下面我会以几个经典的算法面试题作为引子来进行一个暖场。
字符串匹配问题
首先,我们来看看第一个经典算法面试题,即字符串匹配问题。
说有这样一个字符串,即str1 = "阿阿昀 李阿昀你李阿 李阿昀你李阿昀你李阿你好"
,和另外一个字串,即str2="李阿昀你李阿你"
,现在要判断str1
是否含有str2
,如果判断存在,那么就返回str2
子串在str1
字符串中第一次出现的位置,如果没有,那么则返回-1,并且要求用最快的速度来完成匹配。
大家好好想一想,如果这道题给到你,你会怎么做呢?如果你没有学过算法,例如KMP算法,那么一般来说你是会采用暴力匹配这种方式来进行解决的。大家好好看一下,你是不是像下面这样来进行暴力匹配的?
- 先用
str2
子串中的李
来匹配str1
字符串中的第一个字符,看看能不能匹配成功,结果发现匹配不成功。 - 于是,继续往下匹配,这时匹配的是
str1
字符串中的第二个字符,结果发现还是匹配不到。既然匹配不到,那就只好继续匹配了,这时匹配的便是str1
字符串中的第三个字符了,可结果发现还是匹配不到。那就继续再往下匹配吧!