45、圆圈中最后剩下的数字

经典的约瑟夫环问题。

• 当队列长度为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))