剑指offer—圆圈中最后剩下的点 解答

剑指offer—圆圈中最后剩下的点

题目描述

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

思路

集合模拟环

使用一个ArrayList模拟环,在集合长度大于1时,循环删除指定下标元素,最后留下的元素就是结果

  • 如何确定每次删除的元素的下标

    每次循环对删除元素下标累加,累加后为下一个待删除元素下标,如果超过集合长度,需要循环减去集合长度

  • 流程

    1. 维护一个删除元素下标变量count,维护一个变量num存储每一次循环的集合长度的下标,第一次删除元素下标为m-1,count = m-1,循环结束num = 8
    2. 如果count>num,说明删除下标大于集合长度,需要环型循环,执行count=count-num-1,直到count<=num
    3. 这时拿到的count就是对应删除元素在集合中的下标,执行删除
    4. 从当前元素往后移m,count += m-1
    5. 长度下标减一 num--
    6. 继续循环,直到集合元素长度为1
    7. 获取并返回该元素

代码

import java.util.ArrayList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n==0) return -1;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int count = m-1;
        int num = n-1;
        while(list.size()>1){
            while(count>num){
                count = count-num-1;
            }
            int i = list.remove(count);
            count += m-1;
            num--;
        }
        return list.get(0);
    }
}