00:00
好,我们继续来学习这个数据结构和算法,下面呢,我们来举几个实际的例子,激发大家的一种对这个数据结构一个整体的认识,咱们班应该有很多科班出身的。对吧,就说这科班出身的早就回家去了,现在是吧,还在吧,还在啊,OK,那么我举个例子看大家看这有段代码是一个字符串。OK,然后呢,我这里有一个replace all。替换好,现在问题来了。这些替换的方法其实你是用别人的,那么我的需求变成这样子了,是写出单链表表示的字符串内及字符串节点的定义,并依次实现它的构造函数,计算字符串的长度,串赋值,判断两个串的相等,求子串两串衔连接,求子串在指串中的位置的七个成圆方法要你自己去写。而不是用它的函数,你能搞定吗?
01:02
好,其实这个不难,那现在呢,我给同学们整体看一下我们数据结构一些核心的有哪些,那这个时候呢,老师就打开以前我学的东西跟大家分享,其实你们也不要学的太深,你们只要把我们以前学的学会了就可以了啊大概有哪些东西呢?链表。我们来看看当时链表我们有哪些题,其中有题我们来看一下啊,简单给他搂一眼,虽然大家不一定马上去做,对吧?看当时我们的链表是这样题。这个是求最大值函数的,当时应该是用C加加讲的,我记得是啊,然后接着往下看。当时我那个题是从哪来的呢,就这。看这当时我们做的题,就是刚才我说的,就是用单链表来实现字符串的一个定义。哦,这个题这是字符串链表的,我们再来看一个。这个战和队列。
02:01
战和队列呢,也是一个重要的,也是战和战是一个数据结构,队列是另外一个数据结构来看这个,当时我们还当时用这个来进这个铁路。列车的一个调度啊,也是用站和站和这个队列来来实现,你看。对吧,而且当时我们的这个作业很多啊,你看你看了是不是还是很多的。哦,这么多题。好,我们再来看一个作业啊,这个树与森林,这个森林不知道写错了啊,他就写错了。森林,我们看这个森林有哪些题?我来看一下。我记得当时这个提问也是很多,你看诶把这个怎么变小了啊变小了。放大一点。放大一点你看。当时呢,也是画了这种很多树,很多树,其中一个叫做线,线索画二叉树,对我们这个使用是非常有帮助的,比如右数啊,左数啊这些,你看这个。
03:02
你看这些数,大家应该说最小堆,这最小堆用法呢,它能够快速的进行检索啊,进行检索,你看这些还有对应的二叉数等等。OK,看这前序便利。拿到一棵树。这边也有很多其他的各种数,对吧,还有用它来进行这个通讯电文的一个编写。这些你要是有一个印象的话呢,对我们这个编写一些程序也是非常之有帮助的,好这个呢,其他我就不一个看了,还有像这个图哦,对这个可以看一下,这个叫做搜索。搜索,搜索的话,同学们要去学的话呢,集合和搜索其实是我们开发中经常用到的。啊,我看看当时应该也是做了很多练习。大家看一看,诶这个题看这当时是对这个数进行一个搜索,现在这个公式大家可能看不懂了是吧,可能好好多好久了,放了好久了。
04:02
你看这地方,我们当时这些公司都在用。啊,那你这个有了这个公式,那么检索起来速度确实很快。啊,就求最短路径。求,求这个树的高度。还有二叉树的这个多种形态。对吧,等等对吧,看这个地方就很有用了,当时我们写一个叫做最优二叉手术,最优二叉手手术确实很厉害,这个上去过后,直接对这个效率提升是非常高的。你看这个,当时我们写的这个最优二叉搜索树,当时我记得那个时候特别习惯考什么题呢?就是上来过后让你写棵树。啊,上来给我又让你洗棵树啊,一看到树我就我看到路上一看到树,诶这个跟二叉树很像的样子是吧?啊好这个呢,大家这个在后面呢,我们都会提到啊,后面我们都会提到,好接着我们继续往下讲吧。继续往下讲,那么诶这个是。
05:00
这个不要啊,这个不管它好,我们看了一个大体的有个认识过后,我们接着往下看。那么这有个五子棋,同学们晚上可以想一想,如果我给你一个五子棋,你能不能够算写出一个算法?能够判断红旗是那个蓝色的起因还是黑色的起因,大家可以想一想,其实这个算法很简单。啊,你比如说以前我们在写代码的时候,写两个坦克,这有两个坦克,这个坦克打出一个子弹,一个抛物线过去。啪,打中他了,一打中这个东西知道过,马上爆炸。诶,但是很好玩的,很好玩,那一爆炸这个你就看他什么时候击中他了。啊,有些地方是发一个炮弹出来,这个炮弹呢,它本身也有一个有一个范围,只要碰着它的边也爆炸。啊,这些都可以用算法来实现,这是一个五子棋的算法,很简单,这个不算难,这是最简单一个,就是两只要,只要什么呢?只要这个。
06:07
连在一起了,555铢五颗,只连在一起就算是银,可以想一想再看一个。再提出一个编程的使用的丢手帕,丢手帕呢,我们后面要用链表,环形链表来解决。他这个问题我在前面已经提过了,再说一下就是有一堆小孩。就是有一堆小孩围在一起。那围在一起过后呢?他们开始丢手帕。他们开始丢手帕,那么丢手帕的时候呢?假设这是一号,这是二号,这三号,这是四号,这是五号,假设我们从五号开始数数,数两个数一二号,这个人出出了出圈,然后又从下一个又数一二,这个又数圈,最后留的是谁?好,这个呢,可以用我们的环形队列实现,也可以用我们的环形链表实现,我们再看一个。在很多公司在面试的时候呢,也会出这种很有意思的算法题,比如说邮差最短路径,汉洛塔八皇后。
07:09
那当时我记得以前有一个就是谷歌公司做了一个算法编程大赛。算法编程大赛的话呢,这个很多这个编程爱好者都参加了,你比如说公交车扔石头画图,还有这个呃,求和男子等等,反正其很简单,就说法很简单,但是你就说不出来。啊,做出这个呢,同学们慢慢去看,我给大家说哈,你们如果有兴趣可以可以适当的去看一看,我记得当时应该是有些资料的。呃,我们当时那个参加这个大大赛的时候呢,有很多,呃,他这边是你看这答案都在这里面。这边是一个磁盘问题。是吧,你下面呢,它有各种这个说明,最后让你把这个磁盘给解决了。啊,就说你们只记住一句话就行了,记住老师一句话,反正你想拿高工资,你想拿,比如说你要拿个三万四万的或者更高,你要么是架构比较厉害,要么是业务比较厉害,要么就是你算法比较厉害,不可能。
08:13
写个增删改查你你就拿工资不,不可能事,你就记住这一句话就行了,其他我就不再多说啊,其他你自己去想。对吧,你说哎哟老师,我趁着这个行情还不错,我去拿工资,那只是短暂的。因为你比如说这个大家觉得行情还不错,那我去赶紧拿工资,很快就会有风一样的人涌进来。因为这个这个大家又容易还能拿工资,就会出现什么情况呢,很多人都是中进来。你只能往上走。你走到哪个程度,就是别人刚入行的两三年的人是赶不上你的,好你这个职业就稳定了,这你就放心,公司老板是离不开你的,他一看,诶,小张不能走,小张这个人技术太好了,我们得留着他。对吧,你去看你小张小李这个技术病,准备随时把它干掉,对吧?好,这是一个问题,好,我们再来看汉诺塔问题,汉诺塔问题呢,其实同学们也可以去想一想,就是过年的时候,你们尝试着去想一想,虽然不一定做出来,但是呢,每次想一想,尝试去看一下这个代码。
09:17
虽然你不能写,但是要尝试看好,这是老师给大家讲的这么几个编程问题,下面呢,我们就来开始讲具体的数据结构了啊,我我先把刚才的几个实际问题给同学们阐述到这里,目的就一个,让大家感觉到数据结构算法不空,因为有很多网上讲的数据结构,虽然讲的很深入,但是你感觉很空。说这个东西到底干什么了,没用好,我现在呢就用几个案例,包括结合老师以前学习的这个过程呢,让大家认识到数据结构的确是有用的,好,这是一段代码。好,这是一段代码,我先放到这儿,然后呢,这里面我提出了一个需求。
10:01
啊,就说如果我们自己用单链表来实现也是可以的。其实数据结构你也不用说看多深入,你只要把。你只要把这个大学里面的那种数据全部搞明白了就够了,我再说一遍,你不用去看太多的东西。大学里面的那个,比如说。讲的那些,比如图树与森林图哈希散列,你只要搞得很明白就够了,我说的我好像师说真的够了吗?就够了,但前提是要搞懂,比如老师我我看了一遍,看了一遍没用啊,你有没懂啊,对吧,你还有灵活运用呢,要运用好,这是我们的第一个,就是要求第二个同学们回去啊,就是在在这个有时间的情况下。你们呢,也可以想一想啊,这个能不能够自己去写一个小算法,就是把这个五字棋的一个算法写出来,这个很简单,为什么呢?你们用SC也可以写用一个。
11:01
就用一个。二位数组嘛,然后你看看怎么怎么去,呃,用那个不同的点,用一表示黑子,用二表示蓝子,用零表示没有子。那么不同情况下,我能不能看到哪个哪哪方赢了?对不对?这不难吗?同学们去动脑筋想一想好,当然我后面也会,就是讲这个数组的时候也会说这事好,这是一个五子棋,引起了思考。再一个呢,就是约瑟夫问题,大家也可以想。就是呃,如果你们用那个环形链表,能不能把它实现,或者不用环形链表,你们用那个环形队列能不能实现。我也把它放到这里啊,只要你善于动脑筋。这个是可以的,这是约收付问题,我们又举了一些什么问题呢?诶我们又举举了一个就是常见的一些算法。啊,比如说像这些最短路径。对吧,我这儿写到这儿,吃饭问题,公交车问题,最短路径,八皇后问题,汉诺塔问题等等等等。
12:07
好,同学们可以去思考。后面呢,这儿还有一个汉诺塔。这还有个汉诺塔其他算法。其他算法,OK,我也把它给同学们放到这儿就是。这么一个题,当时我不是还给大家演示过一个案例吗?还记得啊,这个汉诺塔,汉诺塔呢,我们再看一下,就说这个代码,源代码我们这是有的,同学们可以尝试先回去看一看,在哪里呢?在资料里边我们再给大家看一下代码。在这边我写了一个汉诺塔案例啊,这是这不是在这是在第四个案例里边,汉诺塔我们再看一看,运行一下。CD。啊什么地,然后呢,我们运行啊,就是Java。Java,然后这个to。
13:00
TWER。好,你看这个代码对吧,我们现在自自己这个在动的时候,你看这个地方,你自己先玩一下,就是你先不要用你你肯定首先人要会做。你先自己玩一下,你自己玩完了以后,然后你再自己想办法去,呃,一个个去完成,对这样子做就可以了,你看这样我们我们这样至少能够把第三个一个已搬过来了看。对吧,你自己慢慢去玩,你首先自己会玩了,然后你再去写这个算法。啊,这个地方这个还可以自动演示,我就我就不去看了啊,最后一步一步全部都能够把它实现。这个是不是最优的呢?不一定。最优的算法,大家可以在网上看一看。就是网上呢,它会有很多关于算法的一些讨论的社区,还有一些论坛,大家也可以参与到里面去适当的接触一下,好这个呢,我就不去再去演示了,好吧,好同学就可以好,那关于这个几个实际编程遇到的问题呢,我先给大家提到这。
我来说两句