孩子们的游戏（圆圈中最后剩下的数）

---

题目描述

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

解题思路

把原题简化后：有n个人（0 ~ n-1），遇到 m 报数并出列，然后以下一个人为 0 开始继续报数，报m 出列，如此以往，直到只剩下一人，并返回他的编号。若无人剩下，则返回 -1.

这和著名的约瑟夫环问题一样：

约瑟夫游戏的大意：30个游客同乘一条船，因为严重超载， 加上风浪大作，危险万分。因此船长告诉乘客，只有将全船 一半的旅客投入海中，其余人才能幸免于难。无奈，大家只 得同意这种办法，并议定30 个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从 他的下一个人数起，数到第9人，再将他投入大海中，如此 循环地进行，直到剩下 15 个游客为止。问：哪些位置是将 被扔下大海的位置？

例如：有9个数字 ，从开始到第三个人时出列。

可以知道，当n 对应着9，8，7，6，5，4，3，2，1时，则最终存活的 1 对应的原始位置是：0，6，3，0，3，0，1，1，0

m = 3, f(9) = 0，f(8) = 6 f(9) = (f(8) + m) % 9 = 0, 同样有f(8) = (f(7) + m) % 8 = 6等等。

通过数学归纳法可以得到：f(1) = 0; f(n) = (f(n-1) + m) % n n > 1;

可以通过这个公式解决题目给的问题。

代码

class Solution
{
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m < 1)
            return -1;
        
        int last = 0;
        for (int i = 1; i <= n; i++)
        {
            last = (last + m) % i;
        }
        
        return last;
    }
};

再有一种就是通过双向链表，进行模拟。

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode (int x): val(x), next(NULL) {}
};

class Solution
{
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m < 1)
            return -1;
        
    }
    
    // 构建一个双向链表
    ListNode* head = new ListNode(0);
    ListNode* pre = head;
    ListNode* temp = NULL;
    for (int i = 1; i < n; i++) // 将 1~n-1插入到链表中
    {
        temp = new ListNode(i);
        pre->next = temp;
        pre = temp;
    }
    pre->next = head; // 构成双向链表
    
    ListNode* temp2 = NULL;
    while (n != 1)
    {
        temp2 = head;
        for (int i = 1; i < m -1; i++)
        {
            temp2 = temp2->next;
        }
        temp2->next = temp2->next->next;
        head = temp2->next;
        n--;
    }
    
    return head->val;
};

这个代码：我在VS19上运行没问题，但是在牛客上出现 ListNode重载。不知道为啥？

欢迎各位讨论。

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_46.html

https://blog.nowcoder.net/n/81a858b422804183a1a51dbfd4084ebc