太透彻了:约瑟夫环的三种解法

分享于2021年05月19日
前言约瑟夫环问题是算法中相当经典的一个问题,其问题理解是相当容易的,并且问题描述有非常多的版本,并且约瑟夫环问题还有很多变形,这篇约瑟夫问题的讲解,一定可以带你理解通通!什么是约瑟夫环问题?约瑟夫环问题在不同平台被\"优化\"描述的不一样,例如在牛客剑指offer叫孩子们的游戏,还有叫杀人游戏,点名……最直接的感觉还是力扣上剑指offer62的描述:圆圈中最后剩下的数字。问题描述:0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。当然,这里考虑m,n都是正常的数据范围,其中1 <= n <= 10^51 <= m <= 10^6对于这个问题,你可能脑海中有了印象,想着小时候村里一群孩子坐在一起,从某个开始报数然后数到几出列,下一个重新开始一直到最后一个。不同人用不同方法解决,青铜直接模拟,钻石会优化一下,王者用公式,下面详细给大家讲解思路。循环链表模拟这个问题最本质其实就是循环链表的问题,围成一个圈之后,就没有结尾这就是一个典型的循环链表嘛!一个一个顺序报数,那不就是链表的遍历枚举嘛!数到对应数字的出列,这不就是循环链表的删除嘛!链表模拟并且这里还有非常方便的地方:循环链表的向下枚举不需要考虑头尾问题,直接node=node.next向下循环链表的删除也不需要考虑头尾问题,直接node.next=node.next.next删除当然也有一些需要注意的地方形成环形链表很简单,只需要将普通链表的最后一个节点的next指向第一个节点即可循环链表中只有一个节点的时候停止返回,即node.next=node的时候删除,需要找到待删除的前面节点,所以我们删除计数的时候要少计一位,利用前面的那个节点直接删除后面节点即可这样,思路明确,直接开撸代码:class Solution {    class node//链表节点    {        int val;        public node(int value) {            this.val=value;        }        node next;    }    public int lastRemaining(int n, int m) {        if(m==1)return n-1;//一次一个直接返回最后一个即可        node head=new node(0);        node team=head;//创建一个链表        for(int i=1;ilist=new ArrayList<>();        for(int i=0;i1)        {            index=(index+m-1)%(list.size());            list.remove(index);        }        return list.get(0);    }}递归公式解决我们回顾上面的优化过程,上面用求余可以解决m比n大很多很多的情况(即理论上需要转很多很多圈的情况)。但是还可能存在n本身就很大的情况,无论是顺序表ArrayList还是链表LinkedList去频繁查询、删除都是很低效的。所以聪明的人就开始从数据找一些规律或者关系。先抛出公式:f(n,m)=(f(n-1,m)+m)%nf(n,m)指n个人,报第m个编号出列最终编号下面要认真看一下我的分析过程:我们举个例子,有0 1 2 3 4 5 6 7 8 9十个数字,假设m为3,最后结果可以先记成f(10,3),即使我们不知道它是多少。当进行第一次时候,找到元素2 删除,此时还剩9个元素,但起始位置已经变成元素3。等价成3 4 5 6 7 8 9 0 1这9个数字重写开始找。f(10,3)删除第一个数此时这个序列最终剩下的一个值即为f(10,3),这个序列的值和f(9,3)不同,但是都是9个数且m等于3,所以其删除位置是相同的,即算法大体流程是一致的,只是各位置上的数字不一样。所以我们需要做的事情是找找这个序列上和f(9,3)值上有没有什么联系。寻找过程中别忘记两点,首先可通过%符号对数字有效扩充,即我们可以将3 4 5 6 7 8 9 0 1这个序列看成(3,4,5,6,7,8,9,10,11)%10.这里的10即为此时的n数值。另外数值如果是连续的,那么最终一个结果的话是可以找到联系的(差值为一个定制)。所以我们可以就找到f(10,3)和f(9,3)值之间结果的关系,可以看下图:f(10,3)删除一次和f(9,3)所以f(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这样,我们就不用模拟操作,可以直接从数值的关系找到递推的关系,可以轻轻松松的写下代码:class Solution {    int index=0;    public int lastRemaining(int n, int m) {         if(n==1)            return 0;              return (lastRemaining(n-1,m)+m)%n;    }}但是递归效率因为有个来回的规程,效率相比直接迭代差一些,也可从前往后迭代:class Solution {    public int lastRemaining(int n, int m) {        int value=0;            for(int i=1;i<=n;i++)            {                value=(value+m)%i;            }            return  value;    }}结语我想,通过本篇文章你应该掌握和理解了约瑟夫环问题,这种裸的约瑟夫环问题出现的概率很大,考察很频繁,链表模拟是根本思想,有序集合模拟链表是提升,而公式递推才是最有学习价值的地方,如果你刚开始接触不理解可以多看几遍。如果能用公式递推给面试官说两句,讲讲原理,那一定会让面试官眼前一亮的!- EOF -推荐阅读  点击标题可跳转1、淘宝二面,面试官居然把 TCP 三次握手问的这么详细2、腾讯面试题:64匹马,8赛道,找出最快的4匹最少要几次?3、经典算法面试题:有序矩阵的快速查找觉得本文有帮助?请分享给更多人推荐关注「算法爱好者」,修炼编程内功点赞和在看就是最大的支持❤️