剑指offer-孩子们的游戏

本文为剑指 offer 系列第六十七篇。
主要知识点为约瑟夫环，偏向于数学一点，值得认真仔细的看。

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1；

解题思路

思路1

通过一个环形链表来循环跑圈，每次删除编号为m-1的节点，直到最后只剩下一个节点，就是想要的节点。

思路2

约瑟夫环。
最开始是n个人，m个数字，如果从0开始编码，那么第一个删除的节点k = (m-1)%n,继续向后从0开始对k+1,k+2,……,0,1,……，n-2,n-1进行编号，则前后的对应关系如下。
X -> Y
k+1 -> 0
k+2 -> 1
……
0 -> n-k-1
1 -> n-k
……
n-1 -> n-2
我们可以发现变化后的编号Y和变化前的编号有一定的对应关系，
Y = (X-k-1)%n,对以的X = (Y+k+1)%n,将k = (m-1)%n代入，X = (Y+m)%n，
我们将这个关系用函数表示，F(n,m)表示n个人每次删除第m个数字最后剩下的数字，则上面的关系就变成了F(n,m) = (F(n-1,m)+m)%n,同时很明显的F(1,m) = 0;
进而可以利用递归得到我们最后的解。

解题代码

思路2代码

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n < 1 || m < 1){
            return -1;
        }else if(n == 1){
            return 0;
        }else{
            // F[n] = (F[n - 1] + m) % n
            return (LastRemaining_Solution(n-1,m)+m)%n;
        }
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！