题解 | #孩子们的游戏(圆圈中最后剩下的数)#

题目：孩子们的游戏(圆圈中最后剩下的数)

描述

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

如果没有小朋友，请返回-1

解题思路：这是一种经典的约瑟夫环的问题，因为在这个游戏当中总有人会离开，所以我们可以采用递归的方式来思考问题，首先我们定义n个人，报m次的解是f（n，m），因为n，m以及编号为0的小朋友确定了，所以最后的幸运儿也就确定了，第一次报数m-1的小朋友出列了，接着从第m开始报数，这儿我们定义再次从0开始报数，也就是将所有人的下标减去m即可，也就是最后的幸运儿再加上m，就得到了原来序列的下标，所以最后的解满足f(n,m) = (f(n-1,m) + m)%n。

接下来，我们举例说明：一共有5个人，其中指定的数为3。

import java.util.LinkedList;

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n <= 0 || m < 0) return -1; LinkedListlist = new LinkedList<>();//创建一个链表对象
        for(int i = 0;i < n;i++) list.add(i);//将元素添加/ int remove = 0; while(list.size() > 1){
            remove = (remove + m - 1)%list.size();
            list.remove(remove);
        }
        return list.get(0);//返回元素值
    }
}

另一种解法：

解题思路，因为是环形，所以我们可以构建一个环形链表，使尾节点的next指向头节点。以此对链表进行循环操作，当指针指向下标为0的元素，经过m-1个next后，删除当前节点，将前一节点的next连接到后一节点，直到指针的next节点等于其本身后，代表该链表中只有一个元素，之后，退出循环，将该元素值返回即可。

具体解题方法，如下所示：

上表中第一个箭头代表初始端，其余箭头代表将该数字除去，整体每一行都表示一个环形链表。

具体Python代码如下所示：

# -*- coding:utf-8 -*-
class Node:#构建结构体
    def __init__(self,val):
        self.val = val
        self.next = None

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n == 0:
            return -1
        if n == 1:
            return 0;
        head = Node(0);#创建对象
        cur = head;
        for i in range(1,n):#添加数字
            cur.next = Node(i)
            cur = cur.next
        cur.next = head#将首与尾相连
        p = cur
        while p.next != p:#判断是否是本身，是本身的话停止运行，不是的话继续减元素
            count = 0
            while count < m-1: p = p.next count += 1 p.next = p.next.next return p.val