00:00
上午呢,我们给大家把这个双向链表的哪一块说了啊,我看看把双向链表给大家说了一下,对吧,双向链表说一下,那么我们把这个,呃,把这个笔记给它简单的整理一下,那刚才呢,我们把这个单向链表改成了双线链表,把这个双向链面改成怎么改的呢?我们来看一下这个思路啊,呃,这样子的。把这个整理一下,双向链表的应用实例,包括前面这个代码,给大家放到这边来。是叫double linked list史的DEMO。好把这个先放过来啊,那留了一个,那留了一个问题,大家大家有思路了吗。班长,想出来了没有?没有去想哈,呃,代码在这先留留着,因为大家先想一想吧,好先放这。
01:01
这是我们的这段代码,这段代码我们接着往下边继续来学习。呃,现在呢,我们讲完这个链表过后,有一个问题,就是说这个链表,那它的一个应用场景,咱们来看一个,你学完一个数据结构,它应该有个应用场景来说明它的一个价值,对不对?那。这有一个应用场景,就是单向环形链表的一个应用场景。那么我们这个单向环形链表呢,我们直接就拿到这个实际的一个应用场景来讲解这个问题,我们在前面已经说过了,对吧,就是一堆小孩,他围在一起来丢手帕。那么具体这个要求刚才我已经说过了,里面有三个变量,哪三个变量呢?就是待会儿我们要做的这个事情。是这样的一个事情啊,我们用一个图解的方式再来说一下,待会儿呢也要用,待会儿呢,我们假定有这么七个小孩吧,这也比较好,比较好看。
02:07
就是说丢手帕问题,也叫约瑟夫问题,我们把它排好。好的,那么我们先把这个排一排,对。好,这有几个了啊,有六个了,我们再来一个吧。好,把它排好。假设这有个小孩,那这个七个小孩呢?我们事先给他编一个号,有这是一号。这是一号小孩,这是二号小孩,这是三号。这个是四号小孩。这是五号。这五号,这是六号。这是七号小孩。这这么七个小孩呢,他们围成了一圈,这个线我就不画了,因为待会儿呢,我还要反复的倒腾,这个线我就不画了。大家肯定是个。
03:01
一个一一圈,那这一圈的话,我们待会儿把它做成一个什么样子的呢。待会儿呢,我们有这么一个要求。啊,这样一个要求,这个要求同学们刚才已经看过了。就有这么一个要求,那现在我们把它具体化,我们把它具体化,待会我们看到这个N就等于七。七个人嘛,然后呢,这个K假定我们写四啊,假定是四,代表从编号为四的这个小孩开始报数,那报几呢?啊,这个报数呢,就叫M,我们认为报三下,假设假如数三下,我们先把这个题理解了,那待会儿呢,这个出圈的。这个出圈。啊,出出圈的一个序列,或者叫一个顺序,应该是什么样子的呢?大家应该是这样子的,我们看看,首先你待会儿要把一个。
04:00
呃,要把这个从四号找到,先找到四号。好,四号开始报数了,他先说一,他自己要先数一下啊,自己肯定要从你这开数,你要数嘛,对一二。三好,那么这个六号就先出来诶。这个怎么弄过来他。我我把这个弄到底下啊好呃,假定这个六号就先出来了,六号完了过后呢,待会儿要从哪开始数呢?从七号又开始接着数,七号又数,注意听啊,待会因为这个题理解了,你才知道怎么写,那六号出来以后,下一个人是七号,七号接着数数123,所以说这个三号这个呢又出圈了。诶,我这数啊数三号啊,我写错了啊,就是123对他数三啊,数三下好二号就出圈了,二号出圈过后,下面三号接触123,那就是五号接着出圈。
05:00
五号出圈以后,1233号开始出圈。三号出圈以后,1231号开始出圈。啊,绕出圈以后,这不四号吗,四号是123,它它肯定还是个环形嘛。两个人也是一个环形,那最后呢,这个四号又出圈,最后这个七其实就留在这里面了,其就是代表最后一个人,其实这个一七这个人呢,仍然是一个环形。因为为什么它可以做成一个环形呢?因为它这个like能够能够指向自己吗?那还它仍然是一个,就是自己也是一个环,那最后出圈了,显然就是这个七号,好,同学们待会的顺序就是这样子的啊,我们把它记下来,六二。5314,最后这个17号,那但现在这个题呢,就要求你来做了,周老师,那这个很简单,我们数一下就可以了,但现在突然把这个变成700个人对吧,数四下是四下31,你能数一下你写的出来吗?
06:05
你想这就没法弄了呀,弄了半天说你数完了给我再加7000。对吧,你这个地方就开始你得想一个问题怎么解决,那同学们想,这个题摆在我们面前,你肯定很自然的想,既然是它们是一个环形,那么如果我们把它做成一个环形的链表,然后用一个简单的算法是不是就可以搞定呢?诶这就是他一个很经典的一个应用场景,就是刚才我们所说的小孩来这个玩游戏的,好同学们关于这个题的这个题的分析我就说到这儿了。说到这,那下面自然我们就来怎么样把它搞定好,这是我们一个单向环形链表的应用场景,什么呢?就叫约束付问题,也叫丢手帕问题,这个我记得在我们那个时候啊,经常有面试官来出这种题,因为那个时候我们没有什么大数据的这种,这种方向基本上去了,就是写这种,那个是在我们那个时候最最多是C程序员,C程序员一边一般来讲都会出这么一个很很经典的一个算法题。
07:09
啊,就让你去做,就让你去做好,那我们把这个需求先截个。
我来说两句