孩子们的游戏

问题描述

然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

分析

首先设定了参数step用来纪录报数几次，i用来返回下一次从谁开始报数，但是由于循环条件，最后跳出循环时候没有进行i++ 则直接返回最后一次报数的人。
用if(i>=n) i=0; //模拟环。 初值用i=-1 保证第一个报数从0开始和step=0 保证到下一个人时候是从1开始报数

public class Solution
{
    public static int LastRemaining_Solution(int n, int m){
        if(n<1||m<1) return -1;
        int[] array = new int[n];
        int i = -1,step = 0, count = n;
        while(count>0){   //跳出循环时将最后一个元素也设置为了-1
            i++;          //指向上一个被删除对象的下一个元素。
            if(i>=n) i=0;  //模拟环。
            if(array[i] == -1) continue; //跳过被删除的对象。
            step++;                     //记录已走过的。
            if(step==m) {               //找到待删除的对象。
                array[i]=-1;
                step = 0;
                count--;
            }
        }
        return i;//返回跳出循环时的i,即最后一个被设置为-1的元素
    }

    public static void main(String[] args) {
        System.out.println(LastRemaining_Solution(5,3));
    }
}