面试题62.圆圈最后剩下的数字来源：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcofTopic0,1,,n-1，n个数字排成一个圆圈，从数字0开始，每次从圆圈中删除第m个数字。找到圆圈中剩下的最后一个数字。例如0、1、2、3、4这5个数字围成一个圈，从数字0开始每次删除第三个数字，删除的前4个数字为2、0、4、1反过来，所以最后剩下的数是3。例子1：输入：n=5,m=3输出：3例子2：输入：n=10,m=17输出：2限制条件：1<=n<=10^51<=m<=10^6解题思路：数学解法。（逆推）本题属于约瑟夫环问题。（有点像丢手帕，摊手）关于这个题目，先说难点：数是由一个环状结构组成的。当统计到最后一个数时，不是第m个需要删除的数，需要回到数组的第一个位置继续；每次重算号码，都是上次删除的号码的下一位。对于第一个难点，可以考虑取模；对于第二个难点，可以考虑删除号码的下一位作为下次重新计票的起点，剩下的号码依次排列。（注意数字组成是循环的）考虑先模拟，再求反：（为了体现闭环，这里复制了数组。注意：最后1位取不到时，除第一轮外，每round是以下一轮删除数字为起点，重新统计第m个需要删除的数字）这是模拟后得到的结果。现在我们来反推一下：最终确定的数，这个数对应的index一定是0，将每一轮最后一个数的index位置进行反转，那么假设（n表示数组元素个数，m表示第m个数到被删除，以例1,n=5,m=3):当n=1,index:0;当n=2时，索引：(0+m)%2；当n=3时，指数：((0+m)%2+3)%3;当n=4时，索引：(((0+m)%2+3)%3+m)%4；当n=5时，索引：((((0+m)%2+3)%3+m)%4+m)%5。大致说一下前面的逆推过程，找出前面每一轮剩余元素的位置：当还剩1个数时，这个数的索引为0；向前推回，当还剩2个数时，在上一轮元素索引的基础上，需要增加m个位置，然后对数组中的元素个数取模，得到位置本轮元素的个数，将n和m代入，索引为1；当还剩3个数时，同样加上m个位置，然后对数组元素个数取模（此时数组元素个数为3），代入m，n，下标为1；...对于上面的逆推过程总结：从上一轮向前逆推时，上一轮元素的位置为(currentindex+m)%上一轮元素个数。然后根据这个公式，用代码实现。代码实现类解决方案：deflastRemaining(self,n:int,m:int)->int:ans=0#最后一位为最终保留数#向前推进，从元素个数为2foriinrange开始(2,n+1):#对公式求逆ans=(ans+m)%ireturnans得到结果以上就是通过数学解逆向求解《面试题62. 圆圈中最后剩下的数字》问题的主要内容。欢迎关注微信公众号《书所集录》
