00:00
同学们大家好,那从今天开始呢,由我给大家来讲解一门新的课程,这个课程的名字呢,叫做Java数据结构和算法,也就是说我们这一套课程呢,主要讲的是数据结构和算法的内容。而且呢,我们用的是Java这个语言来进行讲解的,大家都知道在大学里边呢,数据结构大量的是用C和C加加来讲的,所以说。我们这套课程呢,用的编程语言是目前最流行的Java语言,这是第一个要跟大家讲的,第二一个呢,也要给大家先交代清楚,我们这门这门这门课程它包含的目录结构有哪些,我们来简单的看一下每个目录结构将来会放什么样的内容,第一个呢,同学们可以看到在这里有一个笔记。那我们讲完这个课程以后呢,最终会形成一个完整的笔记,这个笔记呢,有目录,有内容,有案例,有代码。
01:07
会放在这个文件夹里边,那么我们单独的还有一个文件夹会存放我们每一天编写的代码,会放在这个目录里边,如果你要看源码的话呢,就直接在这个文件夹里面去找,课件呢,放在这的,比如说我们用到的word文档,我们用的PPT,包括我们的图解,比如说点进去在讲课的过程中呢,我们为了帮助同学们理解这个数据结构和算法呢,会不时的画一些。这个图形就是以画图的方式来帮助大家理解这个算法和数据结构,那么我会放在这一个文档里边。OK,那么PPT是放在这里面的,大家知道啊,就是后面呢,同学们要看PPT就在这来找。那下一个目录是什么呢?软件,就是我们在做这个课程讲解的时候需要用到的软件,我会直接放在这个地方去,大家到时候会在这能够找得到下一个目录,就是我们的视频。
02:10
每一天讲解的内容呢,会分分这个章节,分目录的给大家放在这个文件夹,每一天都会有,那同学们要看视频进行回顾的时候呢,就到这个文件夹里面来找我们的这个视频内容,还有相关的资料。那在讲一门课程的时候呢,我们不可避免的会用到很多资料,我们会把需要用的资料呢,直接放到这里,比如说。像Google算法编程大赛里面的一些需要的一些题,比如说磁盘问题,公交车画图等等,我会放到这里,然后呢,像这里我会分享我们在大学学的时候呢,学的这个数据结构的一些资料,也给大家分享到这里,到时候我在讲课的过程中呢,会给大家做一些介绍。另外一个呢,就是数据结构,经典的应用案例我也会放到这里,比如说像这一个银行排队叫号的小项目汉诺塔,还有迷宫坦克、小球岛家丢手帕汉洛塔等等,我们会放在这里,然后呢,如果我需要一些额外的资料。
03:19
额外的一些文件夹呢,我也会放到这,比如说我在讲课会用到的一些测试文件,我会放到这里,那么在讲课的过程中呢,这些资料也在逐步的完善,OK,好,这是我们这个课程的目录,各个各个目录里面存放的内容做的一个讲解。好,那现在呢,我们就来看一下。为了勾起大家对这个课程的一个兴趣和爱好呢,我先用这样一个开场来引出,首先呢,给同学们讲解一下我们这套课程要讲哪些内容,以及我们的一个授课方式是怎样子的,大家做一个了解。
04:02
好,同学们,我们先来看第一个。我们先来看几个经典的算法面试题。我们先看第一个题,同学们。第一个题呢是非常经典的,它是关于一个字符串匹配问题,说有一个字符串,比如说这里面是含有上硅谷、拟好等,这样一个字符串是十寸一,另外有一个子串是上归谷,你上归骨现在的问题是什么呢?OK,现在的问题是问你实卷一是否包含实转二?同学们,你们先想一想,这个面试题如果拿给你,你会怎么做?你会怎么做?那么它要求是返回十寸二,在十寸一就是。这个字符串。在十寸一这个字串出现的第一次的这个位置,如果没有呢,就返回负一,如果有的话,就返回它的位置。
05:03
而且人家有要求,要求用最快的速度来进行这个匹配,你们想想你们会怎么做?如果你没有学过这个算法,比如说有个算法叫MKMP,这个算法你没有学过,那一般的同学呢,就会采用什么方法来解决呢?用暴力匹配。会用暴力匹配你为什么匹配呢?一般人会这样子,他先用这个上。来匹配第1S是尊一的第一个,看看是不是他发现上不是这个第一个不是归吗?这个是上说他匹配不到,于是他就匹配第二个,还是匹配不到,再匹配第三个,还是没匹配到,然后呢,再匹配第四一个,四个空格没有匹配到,再匹配下一个,终于在这里匹配成功了,匹配成功到这个上和这个匹配成功以后呢,他再匹配这个归。哎,也匹配成功了,古又匹配成功,你看股是不是你也匹配成功,上又匹配成功,归又匹配成功,问题在这里,当他去匹配你的时候呢,发现这边是一个空格,看到没有匹配不成功。
06:13
现在。不同的人就会采用不同的方法来进行匹配。那如果你没有学过算法的话呢,一般会怎么匹配呢?你肯定是让这个上。往后面移一位,就让这个上。跟哪一个匹配呢?跟这个规矩匹配。进这个回溯吗?进这个回溯,然后呢,又往下面走,同学们这个就是。最简单最直接的暴力匹配算法,那这样子的话呢,它有一个最大的问题,就是回溯的次数很多,速度很慢。好,如果你学过这个KMP算法,你会怎么去思考呢?同学们,看我打开这里。刚才我讲的大家最容易想到的方法是暴力匹配。这个你要这么去做,直接。
07:02
你可能就没有这一个工作的机会了。别人会给你。一个小小判断就是,此人不会算法。对吧,那你如果学过这个KMP算法,那就简单了,如果会KP算法呢,你会怎么做呢?你会去建立一个叫做部分匹配表。诶,你会建一个叫做部分部分匹配表,然后呢,通过这个部分匹配表里面的搜索词来进行这个匹配,效率就会得到大量的提升,大幅度提升,所以说第一个面试题,我们关于字符串的匹配呢,我就先提到这里,引起大家思考,就说在我们做算法面试的时候呢,会问问到这样的类似的问题。人家就问你,你的速度要求你的速度。我们再来看第二个经典的。算法面试题,这个题呢,是一个关于汉诺塔游戏的一个算法面试题,它的要求非常简单,汉洛塔我相信很多同学在学这个学习过程中都听过,要求很简单,第一个呢,大家看这里。
08:11
它有五个圆盘。当然这个圆盘其实不止五个啊,最多的时候呢,有64个,他要求什么呢?将A塔,就是将这个A塔的这个盘。干什么呢?移动到这个西塔来。但是有要求,第一个要求是小的圆盘不能放在大的圆盘。就是你在整个移动的过程中呢,小的圆盘不可以放在大的圆盘上,第二点在三根柱子之间,一次只能移动一个圆盘。那同学们想你会怎么做?我们来,我们来玩一把吧,我们来玩一把,现在呢,我这里准备了一个小游戏,打开这里一个资料。我这里有数据结构经典使用案例,我我给他演示一个三个盘子的,来各位朋友走一把。
09:02
CD。我运行一下。我运下这个小程序,Java to OK,运行起来,那运行起来过后,同学们想,你要把这三个盘移动到C盘,你会怎么做?你的思路应该是什么样子的?其实大部分的同学思路很简单,就是说你肯定要先想办法把这两个盘,就是上面的两个盘先移动到B塔。然后再把A塔的最后这个盘移动到C塔,再想办法把B塔的两个圆盘移动到C塔,这事就完成了,所以说你其实就是两个步骤,第一个步骤干什么,把上面的两个盘移动到B塔。然后再把这个A塔的,然后再想办法把这A塔移动到A塔的最底层的这个盘移动到C塔,最后把这个两个盘移动到C塔,其实就三步对不对,其实就三步,那我们来玩一把呗,首先你看我完成第一个先把这上面的两个塔移动到B塔,非常的简单。
10:05
非常的简单搞定。这个地,然后。下一步把这个A塔。的最下面这个盘移动到C塔搞定。最后再把这两个塔,这两个圆盘移动到C塔,这个就很简单了,往这边挪一下,往这个拿过来,再往这边拿过来搞定。三个盘对于我们来说很简单,各位只要你智商正常,基本上就就能搞定,但问题来了。如果是四个盘,如果是五个盘,你怎么做?来,我们再演示一个四个塔的。四个盘的。我们演示一个四个盘的,来同学们看看你现在能不能把这四个塔四个盘移动过去呢?同样我们来运行一下Java套,你看现在的难度。你应该怎么去思考呢?
11:00
其实仍然是原先那个思路,你要先想办法把上面的三个盘移动到B塔。再把这个A塔的最下面这个移动到C塔,最后想办法把B塔的三个盘移动到C塔不就完事了吗?移动到多少步呢?这个其实只要你能移动三个盘,你就应该可以移动四个盘是不是。但是如果是四个盘你搞定了啊,同学们,假如你四个盘搞定了。那别人给你出一个题,一动20个分。你想想,作为一个人来讲,你的大脑反应就不一定有这么快了。所以说这个时候就需要我们用什么方法呢?用一些算法来编程实现。那当然我现在呢,因为这四个盘对我来说对吧,对于我们人来说还是没有问题的,我们来玩一把,看看大家能不能跟上老师思路啊来首先呢,先把移动到B没问题吧,第一步第二步A到C没问题吧,第三步B到C没问题吧,没有问题,第四一步A到B能跟上老师思路吗?第五一步C到A搞定吧,C到对,C到BC到B是OK的,不要搞错了。第七步A第七步应该是什么呢?A到。
12:26
第七步就应该是。第七步我们看是应该怎么走啊,我重新来演示一下,重新开始,我刚才有点乱啊,我们来重新来走一个A到B。A到B没问题,没问题,A到C没有问题,B到C没有问题。A到BA到B没问题,C到AC到A没有问题,C到B。C到A,刚才是C到B没问题吧,对,C到B没问题。第七步A到。
13:03
A到B没问题,第八一步A到C移动过来看到没有?第八步就是我们现在已经完成了,把上面三个塔移到B塔,然后呢,把A塔移动到C塔,没问题吧。现在移到A到C第八一步了,是不是第九一步应该什么B到C。B到C,刚刚思路第11步,B到A。没问题吧?第11步,C到AC到A。第12步,B到C,看到没有?已经很快了吧?下几步我不用说,大家知道怎么做吧?把A的移动到B,再把A移动到C,再把A移动到B,一共多少步?大家还记得吗?一共15步。一共15部。那同学们来了,如果我让你把这个盘。变成五个盘。再变成20个盘,你能搞得定吗?这就很麻烦了,所以这个时候我们算法的重要性就凸显出来,那如果说这道题我让你编程实现,你会用到什么呢?就会用到一个叫做分制算法。
14:08
看到没有这个经典的算法,面试题就会用到分制算法。说说算法无处不在。
我来说两句