经典的约瑟夫环问题。
- 当队列长度为1时，结束while循环，返回结果。
- 每次走m步，其中每一步都要把队首的元素添加到队尾。走到第m步弹出元素。
-
弹出哪个元素，需要举例子好好看一看。
代码实现：
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
if n == 0:
return -1
# 构造一个先进先出的队列
Que = [x for x in range(n)]
Que.reverse()
while len(Que) > 1:
for i in range(m):
Que.insert(0, Que.pop())
Que.pop(0)
return Que[0]
创新的利用数学求解的解法，参考剑指offer的解:
首先，对于从0到n-1的数，我们定义一个函数f(n,m) = last，last表示按照规则每次删除第m个数以后，留下的最后的数字。
我们把剩下的n-1个数字序列做个映射，形成从0到n-2 的序列。这样，对于这个从0到n-2的序列，同样可以用上述的函数f(n-1,m)来表示此时最后一个数是多少。（注意，不同于f(n,m)，二者结果不一定一样的）
这样，由上面知道，f(n,m) = f''(n-1,m)，而f''(n-1,m)又可以通过映射关系，用f(n-1,m)。因此，我们终于找到了f(n,m)与f(n-1,m)之间的计算关系。（相当于状态转移方程），那么用递归或者循环，就都好做了。
如下图，对于左侧所有的元素x，都可以通过P映射到右边。
此时， f''(n-1,m)就等于左侧的其中一个值，而f(n-1,m)等于右侧的其中一个值。从左侧映射到右侧，通过P来映射。
但是我们想达到的目的是，想用f(n-1,m)来表示 f''(n-1,m)，这样可以与f(n,m)联系起来。于是，我们想到了逆映射。
对于其中对n求余数，映射与逆映射都是对n求余数，以及把k带入以后对n的求余消去，需要注意一下。
对于上图，左侧是x，右侧是P(x)。
我们想用f(n-1,m)来表示 f''(n-1,m)，于是有逆映射来表示。于是：
最终得到了，函数f(n,m)与f(n-1,m)之间的关系。
注意，这里的f(n,m)其中n等于几，i最终就要到几停止循环。所以要用range(2,n+1)来保证i最终取n。
于是可以通过循环实现代码：
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
if n < 1 or m < 1:
return -1
#last初始化为0，n=1时，last也就是0
last = 0
for i in range(2,n+1):
last = (last + m) % i
return last
S = Solution()
print(S.LastRemaining_Solution(5,3))
