00:00
好,我们来学习相关算法储备,指针思想,呃,我们说了,咱们这次的课程呢,是要从一些相关的算法储备开始讲起啊,那言外之意呢,就是我们不直接讲这个view的底层,而是先去给你储备一些算法。首先呢,我们先来看,呃,什么叫指针思想指针呢?它跟C语言中的这个指针呢是不一样的啊,咱们通过一个题目来看吧,好,比如现在大家看到的这个题目叫是寻找字符串当中连续重复次数最多的字符。啊,一定注意看,这是连续重复次数最多的,就是像这个A连续重复啊六次,这个B呢,连续重复了七次,这个C呢,连续重复了数不清了,但是它是最多的对吧,这个D呢,也是六次,所以连续重复次数最多的呢,就是这个字符C啊,那比如说A呢,它不连续。哎,A它不连续啊,他是这样交替出现的,但是呢,也不能算,A是重复次数,连续重复次数最多,因为它不连续对吧,所以他现在就问你连续重复次数最多的是什么啊,那么这个题目呢。
01:09
嗯,当然有很多种做法,比如说有同学呢,快速的就能想到,我们可以把所有的子字符串都提出来。哎,比如说所有的子字符串啊,这是这个,这是三位的,这是四位的,五位的,六位的,七位的,八位的,九位都提出来对吧,然后看看哪个子字符串中的文字全是一样的。啊,然后呢,并且还要看它是不是最长的,哎,当然可以,但是这样的话呢,你就会发现你的便利次数特别多啊,因为你要去寻找很多很多就已经不正确的,就已经不是连续重复次数最多的啊这样的一个字符串了,所以他这个时候呢,就会浪费很多的一个,呃,就是效率。哎,就做了很多嗯没有意义的,没有这个,呃没有就本本来可以避免掉的这样子的一些,呃就是重就是呃无用的操作,那这个时候呢,老师就直接给大家介绍指针法,那指针是什么呢?指针就是下标啊,我们在这里直接做笔记,指针呢就是下标。
02:11
哎,那下标什么意思呢?比如说下标零啊,那这个时候呢,我们就可以用变量I来表示它这个啊,然后指针,那就相当于指针一上来呢,指向了咱们这个字符串的零号位置。因为咱们知道咱们JS当中是不是算位置,它一定是从零开始算,对吧,从零开始数,那这个叫做指针,所以指针就是一个下标位置,明白吗?啊,咱们一定要记住,指针就是下标位置,它不是C语言当中的那个。啊,那个那个指针的意思啊,不是不是C语言中的指针啊,咱们在C语言中这个指针厉害了啊,C语言中的这个指针。对吧,哎,可以去操作内存,那咱们JS中的这个指针呢,哎,就是一个下标,下标位置而已啊。
03:06
好,那咱们现在就把这个I指针呢,指向第零位,那么勾啊这个字母正确读音应该念J对吧,但是呢,咱们中国人一般来说都管它叫勾,哎勾这个指针呢,一开始指向一这个位置。啊,那么就两个指针,那这个时候呢,就形成了一种指针思想,指针思想其实呢,是一个非常非常好用的一种思想,因为它为什么好用呢?因为它来源于生活啊,你看啊,什么叫来源于生活,就比如说我现在。就是人人。那咱们就说普通老百姓,咱们怎么去做这题,那是不是左手指向这个字母,右手指向这个字母,然后一个一个的往后,往后两只手指对着是不是是不是,诶然后对着看,诶一到B发现哎呀到这个字母不一样了,那就说明之前的全一样。对吧,诶,然后拿个小本,记住六出现了六,然后这个追上来,诶,然后左手右手又开始比着比着对吧,左手看着这个笔,右手就开始比着,诶比着比着比着比A相同对吧,它就来源于生活。
04:11
啊,你的两个小手指就会去比着其中的一个字符,然后右手呢就开始进行动,对吧,左手先不动,右手动啊,然后发现不同了,再拿小本记下来,B呢,出现了七次,然后呢,再把左手移过来,然后你的小右手小右手对吧,就嘟嘟嘟嘟嘟嘟这么蹦。发现了吗?他是这样子的啊,所以说就相当于这个指针法,它其实就是让计算机去演算一下,咱们这个平时生活中啊,就是啊,咱们小伙伴日常生活中真真正正的会拿手来进行的一些这样的一些操作。那所以说现在的话,我们就可以总结出来咱们这个指针的移的移动规律啊,咱们现在这个指针的移动规律就很简单,就是不管怎么样,这个勾都要后移啊,就是你有没有发现每一次这个勾都是要后移的。
05:01
发现了吗?勾都是要后移的,那这个时候呢,它有一个不同的地方就是哎,对,就是如果I和勾啊指向的这个字不一样啊,如果爱和勾指向的字不一样,那么此时就说明什么呢?说明他们之间的字都是相同的。啊,他们之间的这个字呢,都是连续相同的啊,当然了,我这里少一句话,就是如果I和勾指向的字一样。指向的字一样,那么爱不动勾后移,看见没有就是爱不动勾后移。哎,我把这里这个字体调一下啊,咱们把这个英文字体调成consulor啊,这样咱们看这字母看的漂亮。所以这个就是指针移动规律,就是如果I和勾指向的字一样,那么爱不动,勾后移,那如果I和勾指向的字不一样,那么此时说明它们之间的字呢,都是连续相同的,哎,然后让爱追上勾,勾后移,所以你看有没有发现勾是永远在后移的。
06:08
啊,那这两句话呢,我给大家标红。对吧,这两句话在标红,那这个时候我们来看一看什么意思,就是一上来爱和勾指向的字是不是一样。指向的字是不是一样满足这块对吧?那么爱不动勾后移,爱不动勾后移。对吧,然后这个时候再比,你看I和勾指向的字是不是还是一样,那么此时还是爱不动勾后移。好,再比还是一样爱不动勾后移,还是一样爱不动勾后移,还是一样爱不动勾后移,诶,恭喜你,再比的时候,I和勾指向的字是不是就不一样了?对吧,那纸上的字不一样的话,那我这里就说了,此时说明什么?说明它们之间的字都是连续相同的,为什么,为什么它们连之间对,是不是因为你刚才是爱不动勾后移,爱不动勾后移把他们俩之间的间距给拉大的?
07:03
所以这就说明了,既然它们之间有间距,那就说明它们的间距是产生于爱和勾纸上的字一样在产生的这样的的一个呃,一个不同,对吧。哎,他是这样子的,一个一个一个思路啊,所以这个大家就很简单很简单就能讲明白,那这个时候呢,指向的是,呃,你看指向的字是不一样的,对吧,就说明他们之间是连续一样的,那此时咱们就可以统计一下,这个时候就是统计好时机,把这个A重复了六次,可以记一下。对吧,哎,然后这个时候呢,爱就追上勾勾后移,有没有发现爱追上勾勾后一样。对吧,哎哎,追上勾勾后。啊,因为这说了挨之上勾勾后一,然后这个时候子箱子又一样,爱不动勾后一,爱不动勾后一,爱不动勾后一,爱不动勾后一,爱不动勾后一,爱不动勾后一,然后指向的不一样,统计一下。对吧,然后爱追上勾,爱不动勾后移,爱不动勾后移对对动对吧,哎,然后再追上,追上他的时候勾会后移一下,然后爱不动勾后移,爱不动勾后移按不动对吧,那直到什么是不是直到勾出去了。
08:10
对吧?哎,那直到勾出去的时候,勾是不是现在指向了一个字叫安find对吧?哎,那安迪find当然不等于这个D了,所以此时就会自然而然的再再比一次,那再比一次之后,爱就追上他了,那是不是爱也超过去了?所以这个时候它的循环结束条件就是这个,看I是不是还在它的范围内啊,那范围内就指的是小于它的Les,因为最后一位不是它的Les。减一嘛,这个大家应该知道是咱们字符串的Les减一啊,所以看这个I是不是还小于等于这个范围,就是零到的Les减一对吧,然后咱们就让这个指针呢,就做这个操作就可以了。啊,所以这个你有没有发现,就是咱们老百姓平时对吧,就是咱们平时老百姓呃,拿两个小手指再去比着对吧,或者说是小小小孩子对吧?诶比如说你把这个题交给小孩子啊,你问问你,你你的什么小侄子啊,小外甥对吧?估计你都有小侄子小外甥了,咱们很多同学都当长辈了,是不是,哎,那这个时候你就可以问问他,就可以拿两只小手指啊去做对吧。
09:18
好了,那我们就把这道题咱们就给写出来啊,就给他亲自敲出来,那敲出来的话呢,我们就给它新建一个文件夹,叫储备,呃,储备算法题啊。好,我们把这个编辑器打开,然后把这道题先敲出来。把这个关掉,这是老师写的一个view view的东西啊。把它拿进来。好,然后咱们新建啊,新建的话,这个就叫做呃,指针思想好,我们从PPT啊,咱们就就直接HTML了,好吧,哎,那为什么不用的JS调试啊,为什么不用node JS调试,这是呃。一会咱们还有别的题,一会别的题呢,它有嵌套,嵌套的话,然后嗯,用那个note JS的那个命令行啊,它就那个控制台不高级啊,不如浏览器的控制台级,哎,就是一会老师也给大家准备了别的题,就这个题啊,一会咱们看递归的时候咱们就知道啊先,所以老师咱们在这里就直接新建HTML了,咱们没有必要用node JS去调试它。
10:21
对吧,哎,没有必要用node这样调试的啊。好,我们就直接写script了,好,然后我们把这道题给敲出来,这个题目叫是寻找字符串当中啊连续重复次数最多的字符,那我们先把这个字符串我们给它粘过来啊从这个。PPT上给它粘过来。哎,OK,好,然后这个时候我们就开始寻找了,寻找的话怎么办?指针啊,指针并且是两个指针,I是零勾是一对吧,然后咱们现在继续写,就是当咱们这个I还在范围内啊,还在范围内的时候,那么应该继续去寻找,所以这个时候就用while语句,当这个I小于等于的Les减一的时候。
11:08
啊,小于等于的Les减一的时候这样子的对吧?诶,然后我们再去做这些事情,那这个时候很简单,就是看你现在指向的啊Di项是不是跟T指向的地勾项是一样的,如果一样怎么样,不一样怎么样,当然这里可以用叉的方法。It也是,也是一个意思,就是叉at表示的是div位下标为I的这一位,呃的字符啊,但是最方便的肯定还是方括号对吧?那我们现在把这两句中文,咱们仔细看一下这两句中文啊,你就会发现这两句中文实际上是有优化的空间,就是如果爱和勾指向的字一样,爱不动勾后移。对吧,但是你发现指向的字不一样,是不是勾都要后移。那也就相当于不管爱和勾指向的字一不一样,勾都要后移。
12:01
能明白吗?所以咱们这个代码中勾后移是可以直接写在这儿的。你看没有勾后移,可以直接写在这。对吧,哎,就就写在这就可以了。啊,但是你现在这个程序是死循环,为什么?因为你I现在是小于等于S减一的时候,它就会永远在循环,而你现在循环体当中呢,是没有移动I这个东西的。是没有改变I这个变量值的,所以这个循环会死循环,但是别着急啊,你会有没有发现,就当指向的字不一样的时候,爱就要追上勾勾后一样。对吧,但是I和勾指向的字一样的时候,爱是不动的。所以言外之意就在于你这里没有什么东西语句可以写,因为你这里爱不动,你没有不写语句I不就不动了吗?对吧?难道你写I加等于零对吧?哎,就是不写语句它就不动,所以这个时候你就没有必要去写if语句,那不就言外之意就相当于你把这改成不等于,就是当它不等于的时候才有事做,把else删了就行。
13:03
你琢磨琢磨,就是当爱指向的字跟勾不不相同的时候,不是有事做吗?你看,当爱和勾指向的字不一样。这个时候统计一下。对吧,哎,然后让爱追上勾勾后移。这个时候让爱追上勾不就行了吗?这I等于勾,不就爱追上勾吗?那此时你就可以输出对吧,输出报啊报报什么呀,I和勾之间的文字是相同的啊,I和勾。对吧,哎之间的,呃,文字相同,连续相同。啊,咱们就可以报,哎,很很激动,那你看现在这个外语句才几行,一行两行三行四行,五行,六行七行啊,有效部分也就这么五行啊,这两个大括号不算,但是这五行呢,就已经非常的呃漂亮。啊,就特别像一个精美的工艺品一样啊,就是很漂亮,哎,就你看就循环语句,在循环的时候,让这个勾永远在加一。
14:08
对吧,就这个勾,每一次这个勾都在突突突突嘟嘟往后寻找,但是呢,如果爱和勾指向的文字不一样,爱就会追上勾。对吧,哎,那不就完美的复制咱们这个了,那咱们这时候赶紧运行一下吧,刷新你看是不是报出来了啊,咱们来对一下报零六之间啊,文字相同,你看零。对吧,0123456,注意这是六吧,是不是零六之呀,零六之间呀,哎,就到五位,到这五位下标为五这位嘛,然后六到13,这是13。啊,六到13之间的相同。对吧,哎,然后13~26之间相同。啊,然后26~32之间相等。对吧,爱连续相同,那这个时候其实它连续相同为是什么?那是不是就是当时爱指向的东西,因为你你你比如说爱在这爱不动勾后一爱不动勾后一直到这的时候,I指向的文字是不是就是当时重复的文字,对吧?哎,连续相同,那你这个时候就可以在说补上都是字母什么,对,是不是都是的I指向的那一项,然后它重复了几次啊,它重复了非常好勾建I。
15:23
对吧,你看我就可以把这句话说完,然后我再刷新。看见了吗?他就说八零和六之间文字相同,都是字母A,它重复了六次,六和13之间的字母是B,是不是其次,那这个时候是不是显而易见,重复次数最多的是不是就这个?C13次能理解吗?哎,就非常的简单,就是这就爱勾法解题啊,用这个循环语句,所以这道题其实它也是一道面试题啊,这道题它也是一道面试题,所以它呢,其实说说白了啊,就说白了就是呃会呃会者不难,难者不会啊,你只要会了,你就不会觉得他特别难,但是如果说你你你就是不会,那就觉得他怎么就想不到对吧?好,那这个时候呢,我们就不要让他报,诶我们现在可以进行一个统计啊,就是和当前重复啊次数最多的,次数最最多的,哎来进行比较。
16:21
啊,那你现在可以写一个叫当前重复啊,重复次数最多的这样的一个次数,比如说叫max repeat,或者叫max count啊,就是重复最多的啊,就是max repeat了。哎,咱们设为零,然后咱们现在就可以进行比较,就是如果你的勾减I,这不重复次数吗?对吧,大于了你的max repeat啊,那这时候就让max repeat等于勾减I,它就是。啊,就是如果超过了,哎,就是如果当前啊,文字重复次数,重复次数是不是就是勾减I呀。
17:02
对吧,哎,勾减I,那么超过了此时的最大值,哎,那么它就让它成为最大值啊,就让它成为最大值。没毛病吧,对吧,好,然后这个报我们就给他,呃删掉啊呃,不删掉了我们给他,哎也就留在这吧,就留在这吧。啊,就留在这儿了。好哎,然后呢,我们就可以,呃,把当前的这个啊,就是重复答案就是重复次数最多的。最多的最多的这个字符串啊,叫max char。好。啊,或者叫ma repeat啊,这个是repeat啊。哎,就是次数。好,然后让这个对吧,让咱们这个的地勾下。对吧,哎,第项啊,对不起,带第项哎,就设备它就行了啊,将I指针指向的这个字符啊,存为咱们这个max repeat的叉啊就行。
18:10
哎,然后这个时候让是不是指针爱,是不是追上指针勾啊。啊,指针勾,那为什么要追上,那其实就是刚才这个PPT上讲的啊,当他俩相同的时候,就不用追,就爱不能勾后移就行,对吧?哎,就行了,那极端条件下,比如说这块是打开的啊,比如说极端条件下这块就完全不一样,不重复,那不就是。这俩A和B不一样嘛,那就爱追上勾勾后移对吧?爱追上勾勾后移,就俩就开始进行猥琐前进了对吧?你看又不一样,爱追上勾勾后移,爱追上勾勾后移,他俩就进行这种猥琐前进了啊,但这种情况太极端了。哎,就是这样子的啊,他就进行猥琐前进了。啊,但是刚才那种极端前进是对的啊,比如说咱们现在把这改成极端情况,你看ABABABAB,你看它就会报和连续,对吧,二和三之间相同都是重复一次,没错啊,这句话没错啊,对吧,这是012220123,二和三文字相同,但是它是二和三文字之间的相同啊,啊零和一之间的,这还没往上滚,它是之间的就说明零和零啊,因为这个一是指向了一个新的不一样的字符吗?
19:21
对吧,它是之间的,就是零啊,就是零,哎,就是只算爱这个,不算勾这项,对吧,没问题吧,哎,重复了一次,所以它就相当于进行了猥琐前前进,但是没有问题的啊。好了,就是这样,所以说这块的话,我们把注释比上就是嗯,看I指向的字符和勾指向的字符是不是相同,是不是不相同啊,如果不相同,那么就说明他们之间连文字连续相同,对吧。哎,然后这块是不管相不相同,相同相同啊,那么勾永远要后移。
20:00
所以你看这个代码就写出来了,然后循环结束之后呢,循环结束之后就可以输出答案了,诶我们就可以输出conso dialog叫max啊,Repeat char,哎,重复了,哎,Max repeat count词啊,是最多的连续重复。呃,字符啊就行了,这个就是答案啊,刷新咱们可以看一下是不是C重复了13次,它是连续重复次数最多的。对吧,哎,那这个council diallo就可以注销掉啊,就可以那个注释掉。啊,就没有问题,那如果次数一样多呢,比如说a ABB CC啊,那它只它会以先出现的为准,就是后出现的,因为咱们这里没有写大于等于对不对,没有写大于等于,所以他会以先出现的为准啊,不过这个就已经可以当做面试题的答案了,具体细节不用管,比如说打平手这种不用管啊,因为面试题出你这种题其实考的就是这种指针法。
21:03
哎,考的就指针法,然后大家不要看老师写的这个,呃,注释挺多,但其实如果说我把这个注释给删掉,其实就是五行语句,咱们刚才也讲了,就是五行语句啊,把注释给删掉就是五行很简单啊,这个代码不要觉得它很难。好了,那么这个就是指针法,那指针法的内涵是什么?如果说我现在问问大家,指针法的内涵是什么?对指针法的内涵呢,就是俩字,生活。懂了吧,哎,它就是来自于咱们生活,咱们人类平时啊,然后怎么做他就怎么做,那实际上它的优点呢,就在于这个指针它只向后移动,大家发现了吗?它只向后移动,那这个时候这个指针是不会向前移动的,所以它的时候的算法效率就很高啊,也就是说每个字符它只会被变历一次。对吧,哎,他只会被变了一次啊,就排排坐就走了啊,他就没有那种重复的那种东西,就一旦遇见他俩之间的字不一样,他就不会再去比各种其他的情况啊,所以效率是很高的。
22:06
好吧,哎,大家一定要记住这是什么思想指针思想好,那么请大家把这个代码呢,多多的自己加以练习。
我来说两句