本文转载自微信公众号“bigsai”，作者：bigsai。转载本文请联系bigsai公众号。前言约瑟夫环问题是算法中比较经典的问题。问题很容易理解，问题描述有很多版本，约瑟夫环问题也有很多变体。这篇关于约瑟夫环问题的讲解，绝对能让你看懂一切！什么是约瑟夫环问题？约瑟夫环问题在不同平台上通过“优化”来描述是不同的。比如在牛客剑志offer一个游戏叫孩子，还有一个游戏叫杀人，点名……最直接的感受还是点开offer62的描述：圈内最后剩下的数字。问题描述：0,1,...,n-1，n个数排成一圈，从数0开始，每次从圆圈中删除第m个数（从下一个数开始计数删除后）。找到圆圈中剩下的最后一个数字。例如0、1、2、3、4这5个数字围成一个圈，从数字0开始每次删除第三个数字，删除的前4个数字为2、0、4、1反过来，所以最后剩下的数就是3。当然考虑到这里的m和n都是正常的数据范围，其中1<=n<=10^51<=m<=10^6对于这道题，你脑海中可能会有一个印象，想起小时候村里的一群孩子坐在一起，从一个数到下一个，从下一个重新开始，一直数到最后一个。不同的人用不同的方法来解决。青铜直接模拟，钻石优化，王者用公式。让我在下面详细解释这个想法。循环链表模拟的本质是循环链表问题。围成一圈之后，就没有尽头了。这是一个典型的循环链表！一个接一个，就是链表的遍历枚举！对应数字的出队，这不就是循环链表的删除吗！链表是模拟出来的，这里有一个很方便的地方：循环链表向下枚举不需要考虑头尾问题，直接node=node.next循环链表往下删除不需要考虑头尾问题，直接删除node.next=node.next.next，当然还有一些需要注意的地方就是当循环链表只有一个节点时停止返回，即当node.next=node时delete，需要找到上一个要删除的节点，所以我们删除count的时候，要少计数一个，直接用上一个节点删除，后面的节点可以这样，思路清晰，直接打开代码：classSolution{classnode//链表节点{intval;publicnode(intvalue){this.val=value;}nodenext;}publicintlastRemaining(intn,intm){if(m==1)returnn-1;//一次一个，直接返回最后一个nodehead=newnode(0);nodeteam=head;//创建一个linkedlistfor(inti=1;ilist=newArrayList<>();for(inti=0;i1){index=(index+m-1)%(list.size());list.remove(index);}returnlist.get(0);}}递归公式求解我们回顾一下上面的优化过程，利用上面的余数可以解决m远大于n的情况（也就是理论上需要很多很多圈的情况）。但是，也可能存在n本身非常大的情况。无论是序列表ArrayList，还是链表LinkedList，频繁的查询和删除都是非常低效的。于是聪明人开始从数据中寻找一些规律或关系。先抛出公式：f(n,m)=(f(n-1,m)+m)%nf(n,m)指n个人，报第m个数并列出最后的数，请取一个仔细看我的分析过程：举个例子，有十个数0123456789，假设m为3，最后的结果可以记为f(10,3)，即使我们不知道它是什么。第一次做的时候，找到元素2，删除。这时候还剩9个元素，但是起始位置已经变成了元素3。相当于345678901这9个数改写开始找。f(10,3)删除第一个数字。此时这个序列最后剩下的值就是f(10,3)。这个数列的值和f(9,3)不同，但是都是9个数，m等于3，所以删除的位置是一样的，也就是算法的大体流程是一样的，但是每个位置的数字都不同。那么我们要做的就是找出这个数列和f(9,3)的值有没有联系。不要忘记搜索过程中的两点。首先，可以通过%符号对数进行有效的扩展，即我们可以把序列345678901看成(3,4,5,6,7,8,9,10,11)%10。这里的10就是此时n的值。另外，如果值是连续的，可以在最终结果中找到连接（区别是自定义）。所以我们可以找到f(10,3)和f(9,3)取值的结果之间的关系，可以看下图：f(10,3)deleteonceandf(9,3)sof(10、3)的结果可以转化为f(9,3)的表达式，同理：f(10,3)=(f(9,3)+3)%10f(9,3)=(f(8,3)+3)%9...f(2,3)=(f(1,3)+3)%2f(1,3)=0这样，我们不'不需要模拟操作，我们可以直接获取Relationship来查找递归关系，可以很简单的记下代码：classSolution{intindex=0;publicintlastRemaining(intn,intm){if(n==1)return0;return(lastRemaining(n-1,m)+m)%n;}}但是递归效率比直接迭代差，因为有来回的过程。它也可以从前到后迭代：classSolution{publicintlastRemaining(intn,intm){intvalue=0;for(inti=1;i<=n;i++){value=(value+m)%i;}returnvalue;}}结论我想，通过这篇文章，你应该已经掌握并理解了约瑟夫环问题。这种裸约瑟夫环问题出现的概率很高，调查很频繁，链表模拟是根本思想，有序集模拟链表是改进，公式递归是最有价值的地方学习。如果刚开始接触，不懂，可以多看几遍。如果能用公式递归的给面试官说几句，把原理讲清楚，一定会让面试官眼前一亮！
