00:00
那么我们再来看一个经典的算法面试题叫什么呢?八皇后问题,这个八皇后问题是一个古老而著名的问题,非常简单,这里面会用到一个回溯算法。这个问题是什么时候提出来呢?是这样子的,他是在这个1848年的时候呢提出,比如说我这有八个格子,八乘以八的格子,一共有八个皇后,八个皇后,那这八个皇后呢,他要求互相不能攻击,什么意思?就是任意的两个皇后,就大家看到任意的两个皇后,你任意的两个皇后干什么呢?你任意两个皇后不可以看这里不能够处于同一行。不能处于同一行,同时呢,他也不能处于同一列。就是不能在同一行,也不能在同一列。就这个要求。那么同时呢,还不能在同一个斜线。问,一共有多少个白发?这个问题呢,当时一个叫高斯的人认为一共有76种方案。
01:04
高斯是一个著名的数学家。大家都在小学应该学过,是不是高斯定律?那么实际上后面呢,有些人说有四,只有40种解法,最后有人用图论的方法解除,一共有92种。那我们后面呢,会专门讲这个八皇后问题,的确如果用我们图论的方法来用编程的方式实现呢,的确是92种。确实有92种算法,呃,92种摆法,那现在呢,我们来玩一把,看看韩老师能不能把它做出来啊,首先一共92种,我每让我每一种都试一下,我可搞不定,但是呢,摆一种两种还是没有问题的,刚好呢,网上有这么一个小游戏,我把它打开,我们来玩一会。好,我们来玩一玩,来走一个,我们来看看,现在呢,韩老师给他演示一个啊,我们看看怎样摆出一个符合要求的八皇后的一个格式,来走一个,同学们有兴趣自己也可以玩一玩。
02:05
自己也可以玩玩,好我们来看一下,一共有92种摆法,老师呢给大家演示一个,首先我们给你演示一个错误的啊,比如说你摆第一个在这。摆了一个皇后,那么你在第二一行,你在这第二行,你第一个格和第二格就不能摆了,为什么?如果你在这个第二行的第一个个摆,他们就在同一列,这个游戏就结束了,如果你在第二个摆,他就在同一斜杠,呃,同一斜线也挂了,你看我试一下啊,我直接摆。看。你这一摆他这个地方就下去了,说明什么?他认为这两个是冲突的,明白这意思吧,所以说我们不能这样摆,我们重新来玩一下啊,所以说我这次摆一个正确的,第一个我摆这这个他就不能让你摆了,那下一个我们摆第第二行摆到第几个呢?我记得是摆第五个啊,如果错了我们再调啊,没问题,第三行我们摆在第八个。第八个下一个呢,我们摆在第六个位置,1234566。
03:06
第六一个位置。好,看看这地方这个位置应该有问题,这个第三行我们摆在第八一个位置啊,第八个位置根没问题,然后再摆第六一个位置,123456摆这儿第四行。第第五一个我们摆在第三个位置,看看老师能不能一试成功哈,再下一个摆在第七个位置,第七个位我记得是再下一个摆在第二个位置,没有毛病,最后一个摆在哪个位置,只能摆在第四一个位置,走winner。Winner OK了,说明韩老师的记忆还是比较正常的,对不对?那么同学们有兴趣呢,可以再去玩一玩,他的要求就是刚才老师所说的啊,是不能在同一行,也不能在同一列,也不能在同一斜杠,一共有多少种呢?告诉大家92种。92种。这个呢,我们后面会专门去讲这个八皇后的回溯算法。
04:04
所以你看这个算法还是非常有意思的,我们再来看一个非常有意思的算法面试题,这个算法面试题呢,也是非常经典的,叫什么呢?叫马踏棋盘算法。有些人把它叫做骑士周游问题,这个棋它是什么呢?也是在一个八乘以八的一个国际象棋上面有一个马。这个马呢,他要求这个马按,按照这个马走日字,马是走日嘛,如果走过走过象棋的都知道马马走马走日。那么要求这个码他给你定一个位置,比如说你开始的时候,他可把这个码呢放在一个位置,要求你这个马能够把这64个方格全部抬一遍。应该怎么走?再说一遍,就是这个码按照走日子的方法呢,要求把这一个整个这个棋盘的每一个位置都走一遍。这个就叫马踏棋盘。
05:00
这个用到什么算法呢?告诉大家这个算法会用到我们图的深度优先便利DFS这个算法,如果但是呢,有个问题,如果只是用这个深度优先算法来玩的话呢,这个效率很低。比如说你放在一个位置,可能要算30秒,才能把这个码,它到底应该第一步怎么走,第二步怎么走给你算出来,如果加上我们的贪心算法进行优化呢,这个效率就得到大幅度提升,这就证明算法在不同的场合下,你用什么算法非常的重要。所以你看现在好一点的公司呢,都会有这种算法题。而算法的基础又是什么呢?数据结构,因此我们这个课程本身是讲数据结构和算法,那么同样我们来玩一把这个游戏。打开这个里啊。同样我们点开这儿,同学们有兴趣也可以去玩一玩。好,稍等片刻,他现在呢,要进行一个简单的加载。好,现在开始游戏,那么这道题呢?他为了简化它,其实没有给出八乘八的一个格子,给的是六乘以六。
06:09
六乘以六好,这个呢,我给他演示一个啊演示一个,但是我这次演示是个错的,就说我给你我就乱走,你们看到什么时候他会出问题,后面呢,我们要把这个问题解决,我们要写一段算法题,在哪里讲呢?大家看在我们的最后这个地方,我会专门讲这个马踏棋盘算法。因为我刚才讲过这个马踏棋盘游戏代码的实现呢,这里面涉及到一个图形的深度便利和探寻算法的一个优化。他的东西很多,他的内容很多,我们会放在这里专门来讲,那现在呢,我给大家演示一下他是怎么走的,会为什么又会失败,我给大家把这个游戏简单的介绍一下。好,我就瞎走啊,比如我走这当我走完这个位置过后呢,这个心就代表你已经走过了,意味着这个码现在还有这几个位置可以走,就是有码头的,就是你可以走,我瞎走。
07:04
现在还有这个位置可以走,我在走这儿,我在走这儿,我在走这儿,我在走这大家看,当我走到这儿的时候,你看我已经就死掉了,因为一旦我走,那这个马就不能按照这个马走日子的方法。这个游戏就结束了,说明你一共走了七步,那如果你这个要要成功的话,你看我们刚才是六乘以六的一个格子,理论上说你应该走多少步呢?走35步才是马踏棋盘完成。好,这就是我们讲的这个算法,面试的又一个题,叫做马踏棋盘。好,同学们,那为了让大家明白这一个算法的这个重要性呢,我举了举了这么几个经典的算法面试题,引起大家一个兴趣,我在这里讲这个算法面试的一个题呢,重点就是两点,一个告诉大家算法很重要。
08:00
第二个算法很有趣,第三一个呢,算法学习起来有一定难度。但是呢,真的从目前来看,不会算法的程序员。迟早会被逐渐的淘汰,所以大家呢,要在这个地方要引起一个重视,好我把刚才讲的内容呢,进行一个简单的一个板书。好,刚才我们讲的第一个是内容介绍对吧,内容介绍和什么和这个授课授课方式的介绍,我们先讲了。几个经典的算法面试题引起大家的一个思考。好,我先在这里做一个简单的笔记。好,首先呢,我建设的第一个算法题是不是第一个算法题。OK。第一个算法题放这儿。第一个题呢,我讲的是字符匹配,字符匹配我用一个小的箭头对吧,这边要求是这样子的,第一个要求同学们呢,有兴趣也可以先去想一想怎么做。
09:08
后面我都会一个个讲,第一个呢,一般的人会想的是暴力匹配,暴力匹配效率低。效率低,暴力匹配。它的特点是简单,但是效率很低。效率效率低对不对,那么第二个呢,就是我们在实际这个面试的时候呢,应该用的是KMP算法,这个呢,我会后面会详细的给大家介绍。他是到底怎么做的,这一句话两句话说不清楚,好,第二个给同学们举的这个案例是什么呢?是一个关于汉洛塔的游戏的一个小案例,也是,呃,希望引起大家的一个兴趣,所以说我在这引出了一个汉洛塔小游戏,他的要求也很简单,对吧,就是把这个盘子,把这个盘移动到。由A塔移动到C塔。
10:01
但是呢,问题是当这个盘子很多的时候,光靠我们人一个个去去想,这就变得很困难了,变得很困难。所以后面我们会学一个算法来搞定它,你比如说你比如说刚才我们这五个盘。你看这五个盘。这五个盘你看我这里就写了一段代码来快速的让它完成这个五个盘就比较麻烦了。他要先把这四个盘移动到B塔。然后再把A塔移动到C塔,而四个盘移动的时候,先要把上面的三个盘移动到B塔,再把这个倒数第二个移动到C塔。是不是这个逻辑啊。那一共有多少部呢?当有五个盘的时候,一共就要31步了,我给大家演示一下,你看这里。我这里写了一个自动演示班盘子,你看这里。一步一步给他演示出来的看。他要把这个移动过来,先把四个盘移动,全部移动到这里,你看这里。
11:00
把这个往这边移动到这好,你看这是不是已经把四个盘移动,再把它移动过来,然后再想办法把这四个盘移动到C塔。说他一总是这样一个步骤。你看现在已经到这儿来了,对吧。越来越接近我们最后的结果,好,很快就结束了。那一共是多少部呢?31部。一共是31步,那我问大家,现在假设有十个盘,20个盘,30个盘。你在?这么一个一个去移动。用我们人去这样去思考。他就显然很慢了,所以这个时候用算法来完成是比较轻松的一件事情,好,我先把这个关闭一下。关闭一下。好,紧接着呢,我们又给同学们引出了一个小案例,是什么呢?就是我们经典的八皇后问题。八黄河问题也是引起同学们的一个思考。八皇后问题,那八皇后问题?它是一个什么题呢?它是这么一个题。
12:00
他是要求有八个皇后分别摆在每一行,但是呢,要求不能同同一行啊,同一行不能同一列,不能同一个斜线,这个时候我们会用到什么算法呢?会用到分子算法。就是这个分次分次算法。OK,那同学们呢,我在讲课的时候,我给他做了一个简单的,呃,一个测试,对不对,我们摆了一个92种的,摆了一种算法。那么现在呢?我们再给大家举了一个,就是马踏棋盘算法。这个呢,呃,我们在讲的时候呢,没有给大家演示一个完整的玩法,因为后面我们会有专门的课程来讲解这个马踏棋盘。好,马达奇盘的它的最终会用的算法是哪些算法呢?我给大家看到这里,它最终会最终会用到一个叫做图形的,大家看到会用到图形的一个优先深度优先算法。
13:01
加上贪心算法的一个优化来完成它,后面我会给大家进行一个详细的讲解,好案例呢,我也给大家解到这来,就是马踏棋盘。好,那么经过这几个小案例呢?今年的算法面试题,我希望同学们能够激起或者燃起对学习数据结构和算法的一个兴趣,好,关于这个讲呢,我们将给大家介绍到这里。
我来说两句