00:01
同学们,我们接着来继续讲解数据结构跟算法的下面内容。那刚才呢,我们给大家说了几个经典的算法面试题,对吧?这个呢让大家感受到学习数据结构算法非常的有意思,那下面我们再来看一看,就是数据结构和算法的重要性体现在哪些方面?呃,体现在哪些方面,我个人呢,根据自己的一个工作,还有授课的经验来讲呢,我觉得算法和数据结构有这么几个地方需要大家去注意一下,第一个呢,首先算法是程序的灵魂。这点一点都不夸张,你比如说优秀的程序,优秀的一个程序,它可以在海量数据计算的时候呢,仍然保持较高的一个。运算速度,为什么?就是因为它有优秀的算法在做支撑。举个最简单例子吧,说你买了一辆汽车,这个汽车的外观。
01:02
其实不是最重要的,它跑得快不快,并不取决于它的外观,而是取决于它的这个引擎发动机性能怎么样,是不是这个道理,说你的程序的优秀好坏呢?其实最核心的仍然是算法。仍然是算法,当然算法很多,算法其实有很多种,你比如说大数据,你学大数据的时候呢,有大数据相关的这个算法,有大数据,有大数据的算法,如果你学人工智能和机器学习,那么你会学习到什么算法呢?就是另外一个领域的算法,比如说是图像识别算法。语音识别算法,数据挖掘算法,比如在人工智能和机器学习,它主要是偏这些方面的算法,那我们在学这个Java这方面,我们用的算法有哪些呢?也非常的多。我们这套课程重点会讲十大常用算法,你比如说二分查找算法,非递归的分制算法,动态规划算法。
02:06
还有贪心算法。KMP算法、马塔棋盘算法,还有普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法。那么这里面呢,就会涉及到我们怎么去求一个最小生成数和最短路径,这些在我们做开发用的非常的多,做算法呢,呃,我觉得是时候该学学了。那么还有一点我要跟大家强调一下啊,在学算法之前呢,首先先把数据结构搞定。数据结构里面有两大类,一个是线性结构,一个是非线性结构。比如线性结构里面我们讲的占。队列链表。这些大家都很清楚,那么非线性结构里面呢,主要是图和数。这些我们都会给大家详细的讲解。好,这个就是我们说算法是程序的灵魂,那么再说一下程序里面,他一般来讲你们在学程序的程序里面,它会内置一些框架,比如说你的Spark。
03:01
这样的一些框架缓存技术,像red,你用了这些技术,它的性能会提升,其实这些缓存产品或者一些框架呢,它的底层也是算法。对吧?所以说我们不是每一个人都要去当算法工程师,但是有一个趋势,同学们必须承认,就是目前程序员的门槛越来越高。对程序员的要求越来越高,为什么?因为现在的程序员很多,当程序员很多的情况下,公司就会优中选优。那谁会的多,谁掌握的技术更牛,我就要谁,我就会给谁更高的薪水,是不是这个道理?好,你比如说我就拿我自己实际工作经验来讲吧,以前我在做开发的时候呢,我最早呢,是在unix下面做开发这个服务程序的,就是开发这个服务器的,主要是用来做支撑这个同时在线有多少人,比如在新浪。我们在做这个产品的时候呢,这个UC产品,他就要求你这个上线人数,他的一个规划,它的规模要支撑上千万人同时在线。
04:08
我原先做的时候,我就觉得这个代码写的很OK了呀,就结果呢,在内测的时候都没问题,内测没有任何问题啊,跑的好好的,我心里还暗暗高兴,这很简单吗?结果这个东西一上线,服务器马上就瘫了。啊,然后公司领导就把我叫过来,说,小韩,你这写的代码很垃圾啊。怎么一上线就瘫了呢?我说我也不知道啊。这个时候马上开了个小会,晚上公司最牛的CTO上来跟我们说,把代码拿过来,一行一行的看,他说你这个代码有问题,你根本就没做缓存。就是没有做缓存,因为当当时我我在工作的时候没有这种专门的缓存产品,比像啊memory catch都没有,那个时候都靠自己写缓存,我都不知道缓存是什么。怎么办呢?这个公司这个CTO,这个哥们上来过后,他拉了两到三天吧,给我优化了一下,他也没有说大大面积的改动,就业务逻辑不用动,业务逻辑不用动主要是对这个性能,就是说对你这个业务逻进行优化,算法进行优化,再次上线,坚如磐石。
05:14
这个时候你真的就感觉到,哇,真的是。这个优秀的程序员,卓越的程序员写的代码就是跟你不一样,这是为什么有些程序员一个月。给你七八千,人家老板都有点儿不乐意。对不对?但有些程序员一个月能挣到五六万甚至10万。为什么写的东西不一样,同学们说这这个地方的同学们要确实要加深这个对他的一个认识,那么还有一点我也必须跟大家强调一下,就是目前腾讯面试的门槛也越来越高了,尤其是这个一线it公司,也就是大家所说的大厂。比如说你们,你们经常所说的这个大臣。这个大厂啊,现在呢,他一般来讲在做笔试和面试的时候呢,都会有几道数据结构和算法的面试题,这个负责任的告诉你肯定有。
06:07
你比如说你有机会将来去面试百度,腾讯,阿里谷歌这样一些好的公司啊,比如像外企的。这些他基本上都会有几道数据结构后面算算法题,而且这些题看起来很简单,就是看起来看起来就是从他题上很简单。但是你就写不出来,就是几句话,比如说我给你出一个求一个最短路径的问题,看起来很简单,你就是写不出来。就题题很短。题很短,但是你就数不出来,明白这意思吧,因为它里面会用到算法。还有一点呢,就是我要强调一下,如果你不想成为代码工人,你真的应该花点时间来学习它了,好,这次的重要性我就讲到这,那下面呢,我给大家同学们说一下,简单说一下我们本套数据结构的,呃,算法数据结构算法的内容我打开给搂一眼哈,同学们看一下我们这套课程大致的内容有哪些,同学们搂一搂。
07:09
同学们搂一搂好,这是我们最新的一套数据结构和算法的一个内容,大概呢,我分这么多章节,第一个就是内容介绍和授课方式,刚才呢,我们已经讲了一部分,下面就是数据结构算法的介绍,里面会做这样一些介绍,比如说算法和数据构结构,数据结构算法的关系,几个实际编程问题,线性结构和非线性结构,什么概念,下面呢,我们会会讲到系数、数组和队列。会讲系数数组的一个数组压缩和解压队列是怎么回事,到时候呢,我们会用一个这样的方式来进行验证,包括数组模拟队列,数组模拟环形队列都要讲,链表我们会讲。这个链表的介绍,单链表,双向链表,单向环形量表和约瑟夫问题,这边是具体内容,到时间我们讲单链表的时候呢,会讲增删改造,同时呢,会给同学们讲一下新浪,百度,腾讯的关于单链表的一些面试题,比如说这个链表的一个逆序打印,或者链表的一个呃,一一个reverse,就是就是逆转。
08:15
双线列表呢,也会讲它的增删改查,还有讲一个环形链表的具体应用就是约束付问题。那么我们还会讲站,讲站呢,我们会讲到站的应用场景,站的快速入门,会写一个关于一个你输一个表达式,我把这个结果算出来是怎么算的。那么还会讲它的一个就是综合计算器,还会讲前缀中缀,后缀表达式,后缀表达式呢,也叫逆波兰表达式,这里面会有这样一些内容。还会讲逆波呢,写一个逆波兰的计算器是怎么完成的,会讲到中缀表达式转后缀表达式的一个具体的一个步骤是什么样的,就是一部代码是怎么实现的,因为别人在面试的时候呢,往往不会让你说的那么理论,直接让你干什么升代码。
09:06
这个代码给我写出来就OK,到时候呢,我们再写一个波兰器,呃逆波兰计算器的完整版,支持加减乘除小括号,支持多位数,支持小数,还可以做兼容处理,到这会看我们怎么完成。下面呢会讲递归的内容,递归呢我们会讲到递归的调用机制,然后递归会解决什么问题,讲迷宫问题。这是递归的一个具体应用,会讲八皇后的一个回溯算法。啊,这些东西你看起来简单,其实动动脑筋也不是那么轻松的哦。就是有,有可能面试的时候,别人直接说,呃,请你用Java代码实现一个迷宫回溯,或者是八皇后问题的一个回溯算法怎么写,直接让你把代码写出来,那么后面我们会讲排序算法,排序算法呢?呃,现在最常用的其实就那么三种,爆泡。插入选择,但是这一次我们课程呢,讲的比较深入,我一共会给大家讲八大排序算法,哪八大呢。
10:08
插入希尔。简单选择堆排序,冒泡快速的排序规定和技术排序,我刚才已经讲过了,因为现在的要求很高,所以说保不齐这种大厂,它会让你直接写个堆排序,或者直接让你写个希尔排序,或者是基数排序,基数排序呢,又称之为升级版的统排序。就同学们可能听过这个统排序对吧,基数排序就是统排序的一个升级版,我们讲的是一个更高级的版本。那么下面呢,就是具体的一些算法啊这些内容了,比如说我还会给大家讲算法的时间复杂度,算法时间复杂度呢有这么些,比如常数阶、对数阶,线性阶,线性对数阶,平方阶,立方阶,K次方阶,指数阶,那么每一个阶它到底指的是什么含义,时间频度,时间浮的到底是什么含义,我会通过案例来给大家进行讲解,大家不用怕啊,说老师这里面会不会用到很多数学用的不多。
11:06
可以这么讲,我数学也学的很差,对不对?你只要跟着我学没问题,只要认真听这些都不是那么很难,因为这些东西只是数学的一点基础而已。数学的一些基础而已,并没有像我们想象的那么复杂,除非你将来学这个数值分析,那那个呢,就对,比如你将来学到这个数值分析,这个啊叫数值分析。或者叫离散数学。离散。离散数学,那这个时候呢,可能对要求数学会高一点,但如果我们只是对一个算法的复杂度进行一个分析,要求并不高,并不高,那么算法的空间复杂度呢,我们会做一个介绍,因为目前衡量一段代码优越还是不优越,主要是看时间,时间复杂度。我们会讲冒泡选择插入,我在讲的时候呢,大家看可以看到先做基本介绍,再做算法分析,算法分析的时候呢,都会配备一个图解,就会告诉你一步一步怎么来的,我会把代码一行一行的给它抄出来,然后逐个的分析。
12:15
肯定大家都能听懂,放心好了啊,放心好了,那么还会讲到希尔排序,快速排序,归并排序,技术排序,这叫统排序的升级版,在这里你看到没有堆排序。说老师你不是讲的要讲堆排序吗?没错,堆排序呢,它需要先学二叉树,所以堆排序我们会放在这个二叉树,讲完过后再给大家回头讲对排序理解吗?后面呢,我会对排序做一个总结和比对。查找算法呢,一般的同学们可能学的就是那个线性查找。啊和二分查找,这次呢,我们会多讲两个,一个叫差值查找和斐波纳气,一叫黄金分割查找算法。这四种我们都给他讲了。
13:00
搞不清你什么时候让你写一个分割黄金分割法查找算法,是不是你要把它搞定,那么会讲这个哈希表,哈希表的基本原理,我们会先讲完,这个哈希表是一个基于数组加单链表的一个哈希表,当然我们会自己动手写一个哈希表。对,这个地方借助一个谷歌的一个上课机体来讲,大家一听听完过后就对这个哈希table的一个底层能够做一个比较深入的了解,因为我们是完全自己动手写一个哈希表。而且是实实在在的一个哈希表,如果我们将来把这个单链表换成一个AV l,这个数AV l就是自平衡的。就是能够实现这个平衡的,平衡的一棵二叉树好,那就更牛逼了,那其实就是有点像红黑素了啊,红黑树效率就更高。那么我们还会讲到树结构的内容,树结构呢,我把它分成了两个部分,一个是数的基础部分,会讲二叉树,二叉树会讲创建、便利、查找等等,会讲它的前序、中序、后续、便利,然后呢,会讲顺序存储二叉树,这个顺序存储二叉树是我们讲堆排序的一个前提。
14:16
啊,后面还会讲这个东西,还会讲线性线索化二叉树,那么数的实际应用部分呢,会讲堆排序,霍夫曼树,霍夫曼编码,那同学们都知道,在我们这个做开发的时候呢,这个赫夫曼数啊,在很多。面试的时候都会问到,为什么会用问到霍弗慢数呢?霍夫慢数呢,它有一个最重要的一个应用,它可以实现对数据的压缩和解压,就说我们文件压缩,文件解压,实际上都是有很多是借助于赫夫曼编码的。这个地方的内容其实非常的有用啊,大学里边呢,一般就讲一个如何创建赫夫曼书就讲完了,我们这次呢,会做一个深入的把赫夫曼编码,以及赫夫曼编码的最佳实践也给他讲了,这个编码到底是怎么来的,这个编码到底有什么有什么用,我们会用实际的案例来给大家讲解。
15:15
就一步一步的分析,而且呢会做原理剖析,还有图解,会把这个图给你画出来。OK,还会讲二叉排序数,我就不再一个念了啊,那这这下面我就不念了,平衡二叉数也叫avl数,然后呢,还会讲二叉数和B数二三数,这个属于多路查找数了,然后会讲B数B加数和B心数,那么这里面呃会讲这个B速B加数,B心数呢,主要是为为大家做一个,就说你你要理解这个索引,就是我们讲MYCQ的时候。老师经常会讲这个索引是基于什么什么索引的,对吧?会基于BB数的一个索引,那么它到底是什么含义,在这里会做一个详细的介绍,做一个详细的介绍好讲完过后这个呢,我们会讲图,图在里面呢,我们会讲图的一个深度优先搜索。
16:05
还会像创建啊,这个地方是应该这写多了一个啊。最多一个就是图的创建和深度优先算法。那么八图讲完了以后呢,我们就可以讲程序员常用的十大算法,哪十大算法呢?二分查找的非递归算法,分制算法。分支算法,我会使用一个这样的呃,汉洛塔来进行一个实际的最佳实践的案例演示。动态规划算法呢,会讲这个背包问题,然后KMP呢会讲字符串匹配问题,会告诉大家搜索词和部分匹配值是怎么创建起来的啊,会讲贪心算法,贪心算法呢,我们会借助一个集合覆盖问题来讲解,就是会做一个实际应用的案例。普里姆算法会讲一个修路问题啊,这里面会讲最小生成数,极小联通尺度是怎么创建起来的,会讲克鲁斯卡尔算法,这面会讲一个公交站问题。
17:07
就怎么能够算出它的一个最小生成数。好,会讲什么呢?像这个图啊,还有狄杰斯特纳算法,这个呢,会涉及到一个最短路径问题,就是说我们有很多节点。从这个节点到另外一个节点,他怎么能够找到一个最短的路径?这叫狄杰斯特纳算法。啊,然后呢,会讲弗洛伊的算法,弗洛伊的算法其实会做一个比对呀,弗洛伊的算法和这个狄金斯纳算法到底有什么区别,他们的它的优点又在哪个地方,好后后面会讲马踏棋盘算法。这个呢,我们会实际的把这个案例写出来,然后呢,我们去验证我们这个算法能不能让一匹马把整个棋盘踏完。大家看一下啊,这是我们常用的十大算法,当同学们把我我们讲的这些内容都。
18:00
真真正正的掌握了啊,那我可以这样负责任的讲,你的数据结构跟算法这个水平会做一个较大的提升。啊,就这样子的,而且实际上我在大学里面学的时候呢,大家看到啊,我们在大学上,在在大学的时候,我们学习的时候呢,我们讲的内容其实并没有这么多。啊,并没这么多,你看我在大学里面上的,呃,上这个上的数据结构,大家可以先看一下在清华讲的是什么内容呢?清华讲的内容主要就是讲的这些的内容,递归搜索链表排序数,数组索引图,但是你看算法本身讲的挺少的。而我们这套课程里面呢,把数据结构和算法结合起来了,所以说应该说还是非常有深度的。对吧,对,对于我们这个程序员来讲呢,只要你理解了,对我们理解算法会有一个大幅度的提升,好,这是内容的介绍吧,下面呢,我在花一点点时间给同学们达成一个共识,就是我们在讲课的时候,我会采用一种什么方式来讲,希望大家有一个理解。
19:12
有一个理解好的,那么授课呢,首先我们是课程深入啊,不是说蜻蜓点水,因为我们在录这套课程的时候呢,三硅谷的这个领导啊,也是有要求的,不能说随随便便讲那么一点点就走了。第二个呢,课程要成体系,大家也看到我们实际上是把数据结构和算法结合起来讲的,数据结构里面把线性结构和非线性结构也是讲了的。而且有一点要跟大家强调一下,数据结构算法它本身呢是有区别,同时也有联系。同时也有联系到时间,我们会逐层的分析,而第三个呢,我希望同学们在学习的过程中是高效而愉快的学习,就说能够感受到这个数据结构和算法的这个好玩的地方,就是我们尽量是数据结构和算法还是很有用,一个是很有用,很有很有用啊,很有用。
20:09
第二个呢,很好玩。很好玩,如果说同学们只是觉得这个有用,但是大家觉得不好玩,或者听起来很枯燥,我们这个课程呢。实际上就呃,不太容易让大家去掌握了,因为数据结构大家知道在大学里面。挺难的是吧,你看我这想现在写数据结构算法很重要,但是相对比较困难,所以说在我这呢,我会努力的做到通俗易懂。但是还是有一个前提我要说到啊,就是毕竟它是有难度的。所以同学们在学的时候呢,还是要做好一个准备,就是多少有些地方是需要大家去思考的,我会教大家怎么去看,比如该d bug咱们就d bug,该画图咱们就画图,该做分析就做分析,那么我采用的这个授课方式是这样一个方式啊。先说应用场景。比如说我要讲一个数据结构、算法,我先说应用场景,再把这个数据结构和算法引出来,然后剖析原理,然后分析实验步骤,在实现步骤的时候呢,我尽量用图,比如说我图文并茂。
21:11
图文并茂来讲,就是分析步骤呢,尽量给他画几个图,然后再代码实现,按照这个五步来走,比如说我给大家讲一讲,比如说我讲八皇后和动态规划,我会怎么讲呢?打开这里,我同学们看一下,如果我讲八皇后,在我们这个课程里面,我们会怎么讲?首先我先提出一个问题,说八皇后问题先提出来了。大家一下子,哦,八皇后是这样一个问题,很形象的就思考了,然后我就引出这个地方会用到递归和回溯算法。然后呢,我就马上把这个递归和回溯算法做一个解释会一般会举例,比如说我举一个打印问题和阶层问题,引起大家对递归和回溯的一个回顾,如果同学们知道递归和,那就不说了,如果你没有听过递归的呢,一听也就明白他的。
22:00
这个解决八皇后的一个关键,这个递归和回收是什么意思,然后呢,我们再做这个八皇后问题的一个算法,算法的一个思路分析,比如说我会告诉大家。解决八方问题第一步,第二步,第三步,第四步应该怎么做,在这个讲的过程中呢,我一般会给大家画一个图,我会在哪里话呢?会在我们的这一个。这个地方我们这不是有个笔记吗?诶不是在这个课件里边有一个图解,我会打开把这个图图改图解,打开过后呢,我会根据这个题的一个特点,在这里给你们画一个图,帮助大家理解它是怎么一回事,明白这意思吧,啊,这是我的一个特点,最后当同学们理解这个算法的思路和步骤以后呢,我们再做代码实现。代码实现完了过后,一边讲一边分析,有些地方需要的bug,我就d bug,有些地方需要追一下源码,我们追下源代码。
23:00
对不对,尽量做到深入。透彻,一步到位。最后当我们把这个算法完成以后呢,我们最好再用一个案例来验证我们算法是否正确,你写完了过后,你怎么知道你的算法是写的正确的呢?很简单,打开这个游戏,咱们一步一步走。看看我们92种算法是不是正确的,如果正确对吧,我我肯定不一个92个不全部测完,我挑几个对不对,你说哦,算法的确是能够运用到实际的。这个案例里面的,那就没问题了,好,同学们,这是老师说的这一个讲解的量,这个步骤,最后呢,我还要定一个目标,我们学东西呢,一定要有目标,我的目标是让大家掌握数据结构算法的一个本质。要求同学们能够达到在工作中灵活运用并解决实际问题和优化程序的目的,就是学完了过后一定要有用,不然大家浪费时间来听的课,对吧?学习了一段时间发现没有什么意义,那这个课就很失败了。我希望同学们学完我们上硅谷这套课程以后呢,的确能够用数据结构和算法解决我们工作中实际的问题,而且能够对优化程序提出自己的观点。
24:14
比如开小会的时候,你作为一个组员,你能够给你的组长,给你的这个组组员,其他组员说我们应该在哪个地方做一个优化,那你不就是将你程序员的价值就提升了,你程序员的价值提升了,自然你的这个薪水也就会上升,对不对?好,所以说我刚才讲了一个八皇后是这样讲的,动态规划也是一样的,比如说你看我们在在讲动态规划的时候。你看你看我在讲动态规划,我先先讲一个应用场景,说这有个背包问题。对不对?先把背包问题提出来,然后我们再想动态规划算法是什么?到时候我会有图把这个动态规划算法讲完了,过后呢,我们再回头解决这个背包问题,然后再验证我们算法是不是这样对的。
25:02
好,这样呢,大家学习起来一有兴趣,第二个呢,难度相对来讲就不是那么那么大了,就是不至少不枯燥了,大家只是自己喜欢去学这个东西了,那我告诉大家问题就解决了一大半,说我会让大家尽量的。觉得这个很很有用,又很好玩,还不算太难。而且呢,我们要达到在工作中能够解决实际的目的,好,同学们,那关于数据结构的内容和我们授课方式呢,就先给同学们介绍到这里。就想给同学们介绍这里。
我来说两句