牛客网——剑指offer之孩子们的游戏(圆圈中最后剩下的数)

LeetCode

题目

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

解题思路

题目假设：n=7，m=3

这道题可以用数组+记录下一位小朋友的位置的方法来做

首先创建一个长度为n的数组，每个位置代表一个小盆友的编号信息，然后，每个小朋友记录自己报数时的下一位小朋友的编号信息

0 1 2 3 4 5 6
1 2 3 4 5 6 0

每次报数，当某位小朋友的数字为目标的（m-1）时，将该小朋友A的下一小朋友B的编号，赋值给该小朋友A的前一位小朋友C，自己将编号设置为-1

0 1 2 3 4 5 6
1 3 -1 4 5 6 0

这样不断执行，最后会发现，当只剩下一位小朋友时，他的下一位小朋友的编号就是他自己

0 1 2 3 4 5 6
-1 -1 -1 3 -1 -1 -1

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @author liaochuntao
 */
public class Solution {

    public int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0) {
            return -1;
        }
        int target = m - 1;
        int[] childens = new int[n];
        for (int i = 0; i < n; i ++) {
            childens[i] = i + 1;
        }
        childens[n - 1] = 0;
        int preIndex = 0;
        int index = 0;
        int cnt = 0;
        while (childens[index] != index) {
            cnt ++;
            preIndex = index;
            index = childens[index];
            if (cnt == target) {
                childens[preIndex] = childens[index];
                index = childens[index];
                cnt = 0;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        int n = 7, m = 3;
        Solution s = new Solution();
        System.out.println(s.LastRemaining_Solution(n, m));
    }
}