圆圈中最后剩下的数

有个游戏是这样的：首先，让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。每次喊到 m - 1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0 ... m - 1 报数 .... 这样下去 .... 直到剩下最后一个小朋友，可以不用表演,并且拿到一份珍贵的礼品。请你试想下，哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从 0 到 n - 1)

解题思路

其实这是一个约瑟夫环问题：如果不想死记公式，可以直接模拟游戏过程

import java.util.LinkedList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n <= 0) {
            return -1;
        }
        int bt = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            list.add(i);
        }
        while(list.size() != 1) {
            bt = (m - 1 + bt) % list.size();
            list.remove(bt);
        }
        return list.getFirst();
    }
}

或者使用数组来模拟

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