362_尚硅谷_Go核心编程_数据结构和算法-约瑟夫问题解决(2).avi原创

那现在呢，我们已然构建出一个小孩了，下面呢，就要解决它的一个核心问题，就是算法，你用一个什么样的算法把它这个东西给搞出来。这个就是这个就算法了，算法其实呢不有我们以前讲过算法有固定的算法，比如说一个什么识别算法，语音识别算法，或者是一个什么编码算法，但是呢，也有一些针对一些实际问题解决的，这个也叫算法，就相当于说你自己设计的一个解决方案都可以叫算法，那现在呢，我们就来看看怎么解决这个问题。好，我们想一想这个问题啊，我们想想问题，既然你人家已经给出了说有N个小孩编号从K，然后呢又从几开始数报数去出列，那你就根据它的这个要求，一步一步往下走就行了。对，至少我们应该分析出来我们要接收的几个变量，第一个呢，你有几个，你你这个链表是谁？你要K是什么？数到几就说这个K和M很重要，至于你有几个小孩N，这个不好说，因为你把头节点给我了，我自然就明白你应该有几个好。现在呢，我们来做一个简单的思路分析啊，来，我们写一段代码。

好，来做这个核心的问题。好，把他的这个需求给各位朋友站到这里来。好的。我们现在就要正式的解决它。好朋友们。走到这里来。哎，这个地方不好看啊，这样不好看，我把它稍微的整理一下，开始，那么我们来分析出来，呃，分析它的一个简单的思路。分析吧。分析这个思路，我觉得应该这么做啊，嗯，首先我们应该编一个函数。编写定要定义一个函数，或者编写编写一个函数，这个函数呢，我们比如说取个名字叫count countboy吧，属小孩就是就丢手绢的数小孩。

Can't see you，哎，Play不会叫这个吧，也叫play play game玩游戏，那玩游戏我要定这么几个变量，第一个呢，投纸针，你要给我，你必须给我一个投指针，你不给我投指针，我没法玩，所以说first的小孩，你要给我第一个，你要给我，第二个呢，就是你得给我一个N，这个K。你得给我一个K，你你想从第几个小孩数啊，这个K，这个K呢，我们就不叫K了，K这个含义比较的嗯，不太容易理解，所以说我我呢就直接叫做star number，大家看能不能理解，就说代表从第几个小孩开始数，说第几个，那么这个M呢，我们也不叫M了，我们取个名叫count number，就是你数几个，这样相对来说别人好理解，你你你想干什么，如果你直接写个K和M啊，说实话。你自己读起来比较比较累，别的人呢，也不太理解你是什么含义，说说待会呢，我取个名叫count number，待会呢也是给你好，这样子呢，你就想办法把它遍历，遍历完了这个函数里面最后只留下一个就算成功了啊，最后最后我们我们使用一个算法，算法啊算法干什么呢？留下，呃，按照按照要求要求在环形链表中留下最后一个，环形链表中留下留下最后一人。

一个一个人即可以即完成。好了，那现在老师开始写东西了啊，思路分析完了过后呢，我们就开始写他的东西，叫范。不累。Play game。Play game play game。然后呢，我把刚才的这这几个参数我就不再写了，把它粘过来。这个没有返回值啊，没有返回值就是我也不去返回了，就把东西打出来就行了。

那现在开始做第一件事情。嗯，刚才我们讲过环形只要是单向链表，有一个在删除人的时候啊，有一个特别重要的一个要求，就是它一定有一个辅助节点，所以说这个呢，跑不了啊啊跑不了，所以说我们先来做第一个动作，第一个需要啊，这是第二步，第二步需要设置啊定义。需要定义。啊，定义一个辅助节点。辅助的辅助啊，辅助的指针。辅助指针。指针帮助帮助我们删除删除小孩这第一个，呃呃，这这是刚才说的，还有一个情况啊，也是这样子的，如果上来过是个空，如果它是一个空的，这个空的环形链表咱们就别别去删了，要防止这个问题说空空链表呢，单独处理一下空的链表，链表我们单独的处理一下。

单独的处理一下，这个也很简单，那就if，如果我们传进来头节点的next，它等于一个near，好说明它是个空的链表，就没没法没法玩啊，所以说这个地方呢，做一个控制。好，PF打印出一句话就说空的空的链表没有小孩，没有小孩，那这个就谈不上你粗略的顺序了，那就直接return不玩了。第二个呢，你应该还要做一个，还要做一个判断，就是你十大的number不能够大于。它至少不能大于小孩的总数，比如说统共有五个小孩，但是你说我要从第几个小孩数呢？我要从第100个小孩数，这显然是不合理的，对不对？所以这个地方你还要做一个控制，就是说如果说你大的number大于了这个小孩的总数，你也应该告诉他参数有误。还有，呃，当然这个可以啊，看到number数几下可以是大于你的，比如说你虽然只有一个小孩，我可以数1万下都行，自己数嘛，1234569，这个无所谓，说这面还有一个判断条件，希望同学们加进去，我这先不写啊，给大家留一个，留一个就是判断，判断什么呢？就是大的这个number不能要应该什么呢？它要小于，它至少要小于等于啊，至少它小于等于这个总数，小孩的总数。

那你这个地方怎么做呢？你可以写个函数。你可以写函数遍历一下，看看它有多少小孩，这个地方很简单，就相当于在秀的时候，呃，在负循环，负循环了几次就有几个小孩，这个呢，同学们可以加进去啊，我这先不去写了啊，好，接着我们往下说删除的事。好，先搞一个辅助节点，这个辅助节点我们干脆就叫tell tell节点啊，叫最后啊，先让它指向这个first。这显然是不对啊，因为我们要我们要知道这个派尔一定要指向这个对尾啊，指向环形量，最后一个先给他，然后呢下一步。

下一步，让。让谁呢？让这个tell tell指向指向。环形环形链表，链表的最后一个小孩，为什么要这么做呢？因为tell将来会帮助我们删掉这个，删除它是很重要的一个东西啊，这个很重要，这个非常的重要，因为在删除小孩的时候，Tell非常要用到它，因为。因为为什么需要啊，因为这个tell tell会在删除，删除小孩时需要用到。需要使用到。那我说一下这个思路啊，同学们可能有些同学不理解什么意思了，比如说打个比方，我现在呢，呃，有这么有这么一个五个小孩，大家看我的思路。有个小孩已经形成环境列表了，我先把我，我先把我的思路给他，给他给大家捋一下，然后再写代码。

好，小车是这样子的。好，然后呢，这边指向它。好，然后。好，然后四指向五。无指向一。好，五指相依好。那现在我现在上来过后呢，大家知道首先有个头节点已经指向了。一号。也也就是说，头有一个first的指针已经指向了一号，这个大家应该非常清楚知道。那现在呢，我我需要一个什么东西呢？我的思路这样子的啊，同学们，我现在呢，需要有一个，也还要有一个指针。要指向第五号节点。大家知道这是为什么哈，老师为什么要要这样子做呢？我待会需要有一个这样的指针叫T指针，当这T指针是个辅助辅助指针哈，我需要有个太指针指向这个一号的最后。

那有些同学老师为什么要这样做呢？因为待会儿呢，我们要去删，比如说我让这个我要删除这个一号节点，如果后面没有这个节点，你删除不了。啊对，删除不了，因此呢，我们现在首先需要有一个胎指针指向最后，但现在还没有指向最后，你看目前呢，目前我是这个胎指向first，也就目前是这样一个情况，胎儿呢，他先展示指向他的这个没有用。你先得让胎儿定位到最后一个。啊，低位到最后一个，然后呢，待会儿我要怎么做呢？比如说我们要从第二个数，那你先让它指向第二个。然后呢，他在行，第二个的时候他要跟着。同步往前移动。啊，你移动几下，我也移动几下，好，紧接着它有数数两下，比如说数两下一二，它指到这儿来了，他指到这来的时候，这个这个缝人也要指向这里，好相对于说他说第三号应该变成删除，第三号删除的时候，我我我怎么做呢？我要这么做。

我先让first指向这个，然后让这个这个T指针的next指向它。让他这里面执行它。好，同学们看到啊，一旦我做了这么一个动作的话，其实同学们可以看到整个环形电表，这个就出列了。因为这个一一旦执行它的话，这根线就。断掉了。这个线就断掉了，因此这个就变成一个初恋的一个小孩。我的思路就这样子的啊，我先把我的思路捋清楚，再写代码，就是这样子，然后呢，整完了过后，你这个first又开始数两下，又怎么数了，诶数他说一。二好，五号二，那么我这个我这个分后面这个胎组织呢，也是跟着它同步往后面移动的，我移动这来了，也就说我这个胎永远在你的这个first的后边，好数到这你又怎么出列呢？好先让这个first往前面移动一下。

然后呢，我让这个tell里面的next右指向。你相当于说把这个地方改了。相当于让他。指向他。你看，但我这么一做的话，你会发现整个环形列表只有124了，你三三和五都都被干掉了，好，我的思路就这样子的，同学们啊，好，明白我的思路过后呢，同学们，那现在老师就可以写代码了，我先把思路分析分析清楚了啊，走代码好。好，现在先定位，先定位，先让ta指向环形电表最后一个小孩，那现在走就行了，负循环怎么写，只要这个套。他他要点next。它等于了这个first就说明它已经到最后了，这个大家理解啊，加一个if语句。

就如果tired等next等于first，那说明这个tired呢，就已经到了最后一个小孩了，哎，说明。说明这个胎儿到了，到了最后，最后的小孩，大家看能不能理解最后的小孩。好，那么这个时候呢，我们就毫不犹豫的。Break，注意下面有个动作啊，下面有个动作要跟着联动。Part next。大家看这个能不能理解，就是说你先你第一个不是的话，就接着往下走，直到找到它的这个尾节点啊，这句话是很重要的啊，这句话一样的，要要要注意要移动好，也就是说整个这个for循环结束以后呢，我们这个这个环形链表的情况应该是这样子的，怎样子的呢？好，我先撤回去。好，应该是这样子的了啊。好。

好，应该是这样子的了，就是相当于你的first节点在我的尾节点到这来了。也也就是说，我把for循环走完以后，我们的环形裂变的情况应该是如此这般的，好，紧接着我们来玩一件事情，什么呢？大家看这里，人家说了啊，要从大的number开始走。那也就是说，此时此刻，我们这两个指针要同步的往下移动。我移动了，移动到什么位置呢？移动到你指定的这个start number这个地方去。那我应该移动几次呢？显然我应该移动大的number减一次。为什么要减一次呢？因为你本身已经在第一个位置了吗？比如说我要从第二号开始，第二号开始走，其实我只要移动一次就行了。因为你本身已经在一号了，所以说我们现在要开始移动到大number，注意听这句话怎么写啊，思路要很清晰啊，先移动到让。让。

让first移动。移动到移动到哪里去呢？移动到这个star number，但有有同学说，老师你这个时候为什么不去设置一个，呃，设置一个辅助节点呢，我可以不要了，因为反正我要把它全部干掉嘛，但你要设一个辅助节点，你让这个first节点不动也没有意义，因为将来first也会被干掉的。就first最后也会被干掉。你，你让他不动也没有用，可能第一个干掉就是他。所以呢，First的节点这个时候设置一个辅助，再设置一个辅助节点没有用了，因为它已经是辅助节点了，所以我们删除的时候呢，就以first为准，注意听这句话啊后边。后面我们删除时，删除小孩就以就以哪个呢，就以first为准，就first指向谁，走完了后first指向谁就删掉谁。就为为准啊为准。好了，同学们，那现在老师代码就很简单了啊，走，走几步，I等于一，I小于等于你的start number减一，OK。

我就移动这么多次。啊，我要移动star number减一，如果有同学这样写的话呢，你就这样写啊，如果说老师我这写的是零，那你再把这个等号去掉也是一样的，无所谓啊，这个看你的，看你是怎么理解的，我觉得这个可能大家看起来轻松一点啊，那我我写成这个格式也可以，就说零，然后小于start number减一，就有些同学可能有点绕不过来，所以说我这样写也是没问题的，我说从一，然后呢，小于等于它减一也可以好，然后呢，爱加加。哎，加加开移动，注意移动的时候呢，是呃，这个first和tell都要移动啊，那就是first等于first.next。First往下移动，同时T等于t.next就它们一起移动。

好，这个相对说这个时候整，整完了以后就到哪去了呢？同学们，当这句话整完了以后，你们可以想象，比如说数两下啊。他数了一，他自己，呃，一自己数一次嘛，所以说它就相当于移动到二了。那这个你移动到二过后呢，我的这个胎儿呢，移动到这一了，好，现在已经到这个位置了，紧接着走数M下，数M下其实也是移动的意思，所以说紧接着在移动M次。第五步。第五步，然后呢，移动继续移动啊，继续移动移动。啊移动到哪里呢？让让这个就是说数开始数啊开始数M下开始数。数这个呃，Count number下。然后就删除。然后然后就删除，删除first指向的那个小孩。指向的小孩，来吧，同学们，那这个地方一定是个死一一，一定是个循环。

因为因为你你数多少下，他是最后只留一个人嘛，所以说他一定是个循环for循环来了，大家看能不能跟上思路。说老师怎么是个循环呢？因为你不是删一个小孩就走，你要删到只剩最后一个小孩。说说你肯定是个循环干掉的，那就开始走，说开数啊。开始。开始数多少下，这么多下。那么他数多这么多下，其实也是减一次，因为他自己要数一下。啊，他要数这么多次，因为他自己要数一次，说说他不能移动count number下，而是移动count number减一下，所以说这段代码和刚才很像。Four I。等于1I小于等于can't number减一，然后I加加，然后走，注意听啊，这个地方是一个很很很有就是考大家的一个重点。

啊，你稍微好一点公司他可能会问这些东西好，那么你就等于他了，你等一会过后呢，好，同学们现在可以干掉他了。删除，也就是说这个时候你们可以理解成我们的代码已经指到这儿了。这他是数两下。他数了两下，因为他自己数一下一二好，所以说这个家伙呢，移动到这儿，这个家伙移到这儿了。现在相当于是谁要被干掉呢？三号被干掉怎么删掉它非常简单，删除first指向的节点。删除这个first直线节点。first指向的。指向的这个小孩，那这个很简单，非常简单一句话的事，首先让first往前面走一步，你不能你你让他走一步啊first.next走一步。

哎，怎么回事？Next走一步走一步过后，警就让tell.next指向first。OK，那这句话可以怎么理解呢？这句话就相当于可以这样理解，就是说first已经已经到这了，他写往前面移动一下。紧接着，让他的这个指针指向了first。其实这个三号就被电干掉了，那你干掉的时候呢，你应该把他信息给输出来一下。说谁初恋了？PDF说编号，小孩编号为多少的呢？出列。处理。啊，出圈了吧，出圈。那么我们把它输出来一下，这个地方，我就这样子打一个箭头，表示一个顺序啊同学们，那现在怎么把它编号是多少打出来呢？其实就是first的一个加和的。Number。大家看能不能理解。

好，这个地方就输出来了啊，输出来了，他就是输出来一个小孩，那问题来了，你这个地方没有退出条件啊，他会死在这个地方的，他不仅是，那什么时候代表他整个就处理完了呢，就是只留下什么时候才出圈呢，就是最后那个小孩。就是留下最后一个小孩，咱们就不要再删了，那什么时候才是最后一个小孩呢？大家想一想就说根据刚才这个逻辑，走走走走只有一个条件，最后到了一个条件就只剩下一个小孩了，只剩下一个小孩，他会形成一个什么情况呢？就是你的first和tell相等了。大家要有点想象能力啊，因为你上完了过后，它会最上完只剩一个的时候，再生两个的时候，一三这个first在移动，不就又指向那个那个那个胎儿了吗？所以说大家要有一个想象空间，就是什么时候退出呢？什么时候推出呢？就是只有一个小孩的时候，那么我们可以加一个判断。

判断一下，判断如果。如果啊，这个地方应该有个判断条件啊，我们看一下啊，是在哪里判断啊，处理完了过，删除完了过后。删除完了过后，我们就可以做一个判断，还是在前面做一个判断啊都可以，好像应该都可以都可以OK，那么就做一个判断，如果tell。Tell等于了这个first，说明现在圈里面只有一个小孩了。圈中。圈中。只有圈子中啊，有只有一个小孩了。只有一个小孩，我们就留下这个小孩，但你要把它删掉也可以啊，删掉就是相当于整个就自空了，那加一个判断，如果。Tell。如果这个tell等于了first。那么这个时候就break break过后呢，留下了最后一个小孩，把它也输出来，就是最后出现的小孩是谁，打印出来一下。

最后出圈的小圈啊，最后出圈的出圈的小孩是谁？你可以把它打印出来啊，呃，当然你其实留在最后的这个就是最最后出圈的，我也不写了，最后这个肯定就最出圈的。好，小孩编号，最后这个给你把它打出来，打出来这个first打印出来就可以了，好，现在呢，这段代码咱们就写完了，我们来测一下看看行不行啊，到底行不行我们也不知道，我们试一下啊，我们试一下好的啊，再检查一下。空链表做了一个判断。做了一个辅助指针，移动到哪个位置啊？先把胎二零到最后，再移动到stand number，再数多少次开始数多少次，每次数不停的数，留下最后一个，好，我们来玩一把。好，现在呢，我们要来进行一个简单的测试，Play game。我们来走一个顺序啊，同学们，走一个简单一点的吧。

那么现在呢，就根据刚才老师说的那那那种方式来玩，First，先给他从第二开始数，数几下，数三下。我们刚才设计的应该也是属相下，好，我们这样子好好来玩啊。来保存一下，保存一下，我们先输出一下这个结果，看看有没有问题。周。好，看一下有没有问题。好，呃，这个地方有一个不好看啊，不好看我们这样子，嗯，就是在输出的时候呢，我们换一行。PTFLN好，先换一行啊，各位朋友走一个。走一个。我们看看这个出现的顺序，出现的顺序啊，这个干脆换一横就看起来很难看。洗干吧。西杠不不用这个箭头了。

不，不用那个箭头了啊，这样看起来太太难太难看了，走。好，现在这样一个看起来比较轻松一点。好，第一个是四号4213542135，就是最后一个是五号，我们看跟我们想的是不是一样的啊，注意看这个顺序，我们再分析一次，就验证一下。验证一下啊。好，我们来把这个用自己手动的方式来走一下，看看顺序跟我们想的是不是一样的啊好，首先呢，他到这儿，他到这儿我们来玩一把。好嗯，从第几个小孩，从第二个小孩好，他先移动到这，它也移动到这，没问题，没问题，然后呢，开始数三下123好，它移动三下移动这儿，同样它也移动三下移动这好这个谁四号出列，四号出列我先跟它移动，然后呢让这个地方移动到这儿。

啊，这个地方这个顺序啊。这样子。好，相当于说四号出列了啊，四号出列我们把它拿出去，把它剪，把它复制到这儿吧，我也不去动它。好，第一个是四号出列了，没问题，紧接着接着数。123到这儿来，那么我也数123到这儿来，好，二号出列，二号出列的话呢，我让他的那个指他往前面移动一下，然后呢，让他。让它指向了这个节点。好，这个时候二号初恋。二号处理。好，我把二号挪动，这紧接着呢，我们让这个三号继续数三下，123指到这来了。那它指到这来了呢，它相当于说这个指到这来了啊，这个指到这来，它也数了三项嘛，123，它指到这好，紧接着一号处理。好，一号出列。好，一号出列了，一号出列的话呢，我让这个为指针对吧，一号出列这个，诶我看看一号出列的话。

421看对不对啊，421正确啊，421那最后呃，4211号出列的话，这个指到这儿来啊，只只有这个两个人了啊叫123好三号出列，三号出列各只有最后一个好，这个代码是正确的，这个代码是正确的。好，那就说42135，那这个这个有什么好处呢？就是说如果我们把这个数据量扩大，那我们就简单了，比如说现在。说老师你刚才这个数一下还可以，现在我们把这个数量增加，增加到50，甚至增加到500，对吧，增加到500，我们现在从第20个人开始数，数数多少下呢？数30以下，你看如果现在再让人来做的话，你就就很难做了，我们有这个算法的话，一下就出来了，你看这个顺序对吧，一下就出来了，你看这个顺序。好。

好，这时候输入编号啊，出列看出圈出圈，最后455号出列。那如果说你要用人来做的话，这个几乎就很难很难做了，好同学们，这个代码呢，我们就给大家分析到这里，我把代码给大家整理一下。好代码。直接把代码整体啊，同学们，我把这个代码整体给大家拿过来就行了。包括我们刚才的分析思路，老师呢，就说的很清楚了。好，来放这里了。好的。好，同学们，那关于这一个小孩出圈的这个问题呢，就跟大家先介绍到这里。