00:00
你们将来遇到一些小的算法,大体也是这样子的,先把问题提出来,然后你想。你怎么去玩,然后把这个代码实现。哦,这这个就是一个。套路好,那现在根据我们刚才的思路,首先我先定一个Harper,先让这个Harper定位到相应的位置,就定位到相应位置,那首先我们来整一个整整整这样一个东西啊来。Vav VR Harper。那这个呢,先指向这个first。好。第一步。OK。这个事情我要把它搞定,这个怎么搞定呢?那就循环呗,那你不知道你肯定是Y循环了吗。Y循环处。诶。这边我要来一个。一个实训环。好,那就判断如果我这个Harper,大家看如果这个harper.next。
01:03
它等于了first就代表这个位置我已经找到了,能理解吧。哎,就说如果在这个循环的时候,这个her.next它指向first了。那这个时候我们这个就相当于这个位置就定定位好了,能理解吧,那这个时候就退出,否则的话呢,我让这个Harper继续往下移动。好,当然,这边我需要用一个break able把它包起来。也就是说,第一个工作我已经做完了。哪一个就是第一,第一件事儿已经搞定。好,第二个将first的指针移动到star number,但是有一个前提啊,这个her要跟着动,Her要相应的紧随其后,要对应移动。那这个简不简单呢?肯定也很简单,因为到number别人已经给你了呀。
02:01
统计一个小孩,人家已经不是给你了吗?好,那现在同学们老师代码就开始写了啊,就完成第二个任务,第二个任务是什么呢。A,对,就这个意思。代码简不简单,很简单呢,那就这个是固定的,不要用外循环了,因为这个当number移动到哪一个地方实现,人家是有的,那最好用的是for循环。是不是用for循环,我移动几次0ON tr?Until。诶,这个地方同学们看一下,就当number。走。我这样写对不对。对不对。不对,要是不是要减一。因为你本身这个first是不是已经指向第一个小孩了?假设你,大家想假设我十大number是从第第几个小孩,是从第四个小孩,我这样会移动几下?是不是要移动四下,你看现在我我们刚才不是说了吗?Star number待会我们设计的是四,如果是四号,我我像这样写,我想这样写它是不会,是不是会移动四次,是移动四次指到哪个小孩去了。
03:12
移动四次指向哪个小孩去了,是向第五号去了,是不是你看嘛,你你原先你原先这个呃,你你原先这个first已已经指向了一,那你移动四次,一次两次,三次四次,是不是到五号来了,那就不对,那应该怎么办呢?是不是应该减一啊。简易。就可以了。啊,当然也可以写成一这样子,好,这个是移动的次数,在移动呢,也很简单,First等应该怎么写啊?First等于。first.next。是不是相相当于往后面移动了一下,同样我们这个Harper呢,也像这样往后移动一下。叫first,指向next,往下移,往下移,往下移,好,这第二步我们也做完了第三步。
04:01
第三步第三步我们就开始数数了。第三步就开始数数了,诶,那么同学们想一想啊,你开始数count number是不是相当于也是移动,是不是那这个移动。OK,那这个移动咱们是不是如法炮制啊?那就是还是一个老规矩,那么我们移动几次,先问同学们说一下counter number是不是移动这么多次,移动这么次数的话。UNTIL。Count,然后counter,好,我这样写对不对。不对,我因为自己是不是要数一下。自己数一下,你其实移动的不是三次,是两次。这个能理解吗?打个比方,打个比方啊,我这样写,假设count number是三。我我先问大家,如果count number13按我这种写法会移动几次?
05:03
会移动几次?会移动三次是不是,那移动三次的话,其实你就不对了,因为你假设你看四,它数三下,他数三下就是它自己要数一次123是不是,它其实移动只是两次啊。这个大家都要分析出来,不然的话这个结果是要错的啊,那要减一,这能理解吗?应该能理解对不对,好,那相当于把这个放到这儿。说,其实你会看到这两段代码其实可以合并。是不是可以合并呢?说白了就是你把这个次数再加上这个次数就可以了,是不是可以合并呢?因为它你你这个移动到哪个地方,再第一次数,那这个是可以的,好啊,这个是定位到哦,我看看啊,我们。这个是first开始数数了,哦,可以了,移到这,移到这,那么这个地方是一个循环的过程,大家发现没有。
06:02
是不是他会循环的操作这个事情呢。他数完一次是不是下次还要数,下次还要数,所以说同学们那这段代码呢,我们要用一个循环来做。是不是要循环来做,那就是这样写了啊,同学们while循,因为这是只是做了一次,那还有下一次,还有下一次啊,说整个这个操作呢,要用一个while包起来拿住了。处TRUE。好,同学们看我的代码要,也就是说相相对于这个时候开始呢,开始。开始循环的操作啊,开始开始数数数数按照什么呢?按照给定。给定的值。啊数啊,每数到一个,每数到一个小孩就出圈。就出圈。出圈。那那么什么时候才结束这个循环呢?直到。
07:02
直到圈中,直到,哎,直到。我写的啊,直到。这个单这这个环形链表,环形链表。链表只有只有一个节点。就结束了。好,所以说我们这段代码要把这段放到while循环里面去,那首先呢,我们来做一个判断,什么时候推出呢,如果。如果什么时候代表这个就OK了,就是这个Harper,它如果等于了first。是不是他不停的走,不停的走,最后。就留了一个人了,留了一个人,是不是刚好这个Harper和first指向同一个节点了?好,那如果这个条件满足,就是代表什么呢?只有一个人了。只有一个人了,没问题,那这个时候呢,咱们就怎么样。Break,否则是不是这段代码就会循环的数?
08:04
卡进去。就是我我这个地方,哈哈哈,好,这就就说如果在循环的过程,我发现只有一个人,那我就退出,否则我就反复的做个事情,那么你在这做完这个事情以后,你是不是还有一个任务。你是不是要把这个first指向的节点干掉?是不是要干掉好,这里面还有一个工作,就是将first指向的指向这个节点干掉,我要删除。或者移除,移从这个单线环境里面移除。那怎么把first指向这个节点移除呢?大家不要忘了,我们这个Harper始终是在屁股后边,那我们来看这个动作怎么完成。那也就是说,呃,现在已经出现这么一个情况了。好,我把这个先撤回去啊,同学们,我们测成一个,哎,完整的一个一个图,现在假如情况是这样子,假如情况是这样的啊。
09:03
同学们看清楚了,假如我们这个first指向了六号。假如这个first指向了六号,Harper指向了这个五号,目前是这样一个情况,要把谁干掉?六干掉。那么这个时候咱们怎么做呢?是不是先让这个first往前面移动一下。因为你你要先移动不移动化,待会你把它干掉过后你再移动就不就不好了嘛,先把这个往后面移,把这个。就先让这个first往往前面移动一个,然后让这个Harper的next指向它的这个这个节点,这个事就完成了,是不是?是不是这个道理,那也就是说这个代码应该这么写了,First。往前面移动一下,等于first next。这句话做完了以后,是不是我们这个线就指向他了。
10:04
然后我们让这个Harper。点next。指向哪里呢?指向这个first其实就可以了。是不是?来这样写更好理解,那这样一做,你看这样子画一指向这个first,不就这节点就指向了它吗?那直线塌了过后,你想想下次我们再来玩的时候,这个人是相当于看不到了,但如果你要做的更干净一点,你可以把这个,把这条线也干掉,但是这个干不干掉无所谓,他也会,反正他也进不到这个圈了,因为我便利的时候,他始终始始终是从范时代走的,他也找不到他了。好,这个代码就写完了。好,写完了,那不停的这个反复的做,反复的做,最终我们这个就留下了一个人,哪一个人呢?好,我在这把这个信息打出来。那么我在这把谁打出来呢?把这个出圈的信息输出来。
11:00
输出。输出,如果你愿意,呃,你还可以把这个信息放到一个队列里面去,到时便利一个队列也可以,所以说将来数据结构可以综合使用。就是队列里面呢,呃,就是说列表里面也可以使用到队列,那我这就简单一点就输出。输出这个出圈。出圈的这个人的信息能理解哈,同学,那我把这个喜欢大家。把这个代码发下去,大家先理解一下啊好,呃,这个几号小孩。这个编号出圈了。出圈OK,那为了好看呢?我打一个这个换行出圈的人是谁呢?是first,点这个number,大家能理解,刚才已经说过这事了,对吧,那整个这个外循环出来以后,应该只剩下一个人了。当while循环结束后。当外循环结束后。
12:00
结束后干什么呢?这个只有一个人了,只有一个人了,那最后这个留在圈里面人,我们把它输出来。答出来啊,最后。最后留在。牛在。留在这个圈里的圈的人是谁呢?好小孩编号为。好,我们小孩编号。那编号为多少呢?百分号D好百分号D呃,百分号D那呃,诶这个地方我们还是用这个格式化,格式化输出。这时我们用这个helper来访问和first访问都是一样的,因为他们已经相等了。那就写点number。好,整个这个while循环,不要忘了用break able把它包下。Break able把包厢。好,我在这儿写到这里来。
13:00
好同学们,那这个原生的啊,原生的这个代码我们就写完我们来。用用看看有没有问题,看看这个面表能不能用好,我们直接在这调一下。这个方法调研这个方法啊测试。测试这个,呃,这个代码啊,测试我们这个count boy这个方法是否正确。呃,那就点吧,看boy我们传值,根据刚才我们这个分析,我们传的值分别是七啊,分别是437。四。代表从第四个人开始数,数三下,一共有七个人。我们看看这个出现的顺序,跟我们想的到底一样不一样啊,走一个。好,我们可以看到小孩出现数,意思是625314。
14:04
七对不对?6253147是不是完全正确的呀?好,是没有任何问题,那这个时候就如果说同学们愿意把这个数据整的再大一点,比如说我有70个人。对不对,然后呢,你知道这个幸运是幸运的人是谁吗?对不对,比如说从41号一共有72最后幸运留在这个圈里面的人呢,就是这个问这这个人最幸运的对吧?你看就是18号人是最幸运的一个人。就约瑟夫问题呢,呃,也是有有一个很经典的小故事,他说好像是,就说有有一堆人,这个一堆基督徒被被被谁抓起来了,然后说现在围成一圈,最后留在圈里面的就是幸运的人,如果你知道这个是吧,你就知道你应该站在哪个位置,你就不会被杀掉啊,不会被杀掉,好,这是我们的一个环形单销链表的一个应用实例,老师呢就讲到这里,我把代码给大家整理一下。
15:02
在吗?在哪里呢?好。这是我们的一个代码。就是环形单向链表的一个应用,就是这西的啊。写到这来。我们就用它来做了一个设计环形单单向环形链表。单向环形链表的一个应用场景,我把这个呢给大家拿过来。啊,给他拿过来,然后呢,这边我们这个分析和代码呢,我也给他放过来就可以了,就是这段代码。应用实力把它拿过来了啊。好,放这儿。好的,那么具体来说这个代码和分析代码。和分析如下分析。先把这个分析给他拿过来分析呢,我们是一步一步分析过来,就用这个图吧,把这个图放这就可以了。
16:01
截点图。一个是。这边的。一个示意图,好,这是我们分析的一个具体案例。对,具体案例,然后呢,这边还有一部分代码,我把它一个抽签的顺序给他分析了一下。思路是在这儿写的。哦,这是我的一个思路。给大家放在这里。啊,代码,然后呢,我们把这个代码放到这儿,代码实现。代码实现呢,就是刚才咱们写的约瑟夫。整个放到这儿就OK了。好,那截取一段视频。
我来说两句