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

2018-05-07

编程练习

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

思路：想到用循环链表来做，但是觉得构造这个循环链表太麻烦，所以就另辟蹊径。想到了用ArrayList来模拟这个抽小朋友的过程。

　　算法的主要思路如下：利用Arraylist来盛装所有代表小朋友编号的数字，即0,1,…n。然后通过m来确定需要移出的编号，再利用subList来重新构建移除特定编号后的新的list。例如：n=5,m=3.则第一个要移除的是[0,1,2,3,4]中的[2],但是我们只关注最后一个得大奖的小朋友，所以这个移除的元素不是我们关注的重点。重点是移除后需要构建新的list，利用sublist方法，将2后边的元素截取2为[3,4]，2前边的元素截取为[0,1]，则新的list就是这两个list的拼接即[3,4,0,1]这样对这个新的list再做递归的截取即可。注意：当m%n==0时截取方法会有稍许改动，以及当list只剩两个元素时可用特定方法简单判断出谁是最幸运的那个小朋友。
java代码如下：

import java.util.ArrayList;
import java.util.List;

public class LastRemaining {
    public int LastRemaining_Solution(int n, int m) {
    	if(n==0 || m==0) {
    		return -1;
    	}
    	//盛装代表小朋友的编号
    	List<Integer> arrlist=new ArrayList<Integer>();
    	for(int i=0;i<n;i++) {
    		arrlist.add(i);
    	}
    	int i=0;
    	//调用helper函数来计算最后一个获得大奖的小朋友的编号
    	i=Helper(n,m,arrlist);
    	return i;
    }
    /**
     * 算法的主要思想：利用Arraylist来盛装所有代表小朋友编号的数字，即0,1,...n。然后通过m来确定需要移出的编号，再利用subList来重新构建移除特定编号后的新的list。
     * 例如：n=5,m=3.则第一个要移除的是[0,1,2,3,4]中的[2],但是我们只关注最后一个得大奖的小朋友，所以这个移除的元素不是我们关注的重点。
     * 重点是移除后需要构建新的list，利用sublist方法，将2后边的元素截取2为[3,4]，2前边的元素截取为[0,1]，则新的list就是这两个list的拼接
     * 即[3,4,0,1]这样对这个新的list再做递归的截取即可。注意：当m%n==0时截取方法会有稍许改动，以及当list只剩两个元素时可用特定方法
     * @param n 小朋友的数量
     * @param m 设置的报到数
     * @param list 辅助的ArrayList
     * @return
     */
    public int  Helper(int n,int m,List<Integer> list) {
    	int flag=m%n;
    	int r=0; //定义返回的结果，注意每一层递归都要返回
    	/**
    	 * 注意：当list中只含有两个元素时就不需要截取list了，因为这就像小时候玩过得点兵点将一样，只剩两个小朋友，非此即彼
    	 * 而到底是哪一个，只和m是不是偶数有关系，如果m是偶数，那么倒数第二个移除的元素就是list中的第二个元素，所以剩下的
    	 * 第一个元素就是那个最后获得大奖的小朋友的编号，奇数反之。
    	 */
    	if(list.size()==2) {
    		if(m%2==0) {
   			 	r= list.get(0);
   			 
   		 	}else {
   		 		r= list.get(1);
   		 	}
    		flag=-1; //为了让下面的flag==0不再执行，因为m=10,n=2时满足flag==0，但是很显然这个地方是递归的最后，我们不希望再执行后面的代码。
    		return r;
    	}
    	/**
    	 * 当m%n==0时，即比如m==n的情况
    	 * 例如m=n=5,此时的list是[0,1,2,3,4]，因为m=5,所以此时需要移除的元素是最后一个，所得到的下一个list是[0,1,2,3,]
    	 * 截取算法和常规情况有稍许不同
    	 */
    	if(flag==0) {
    		List<Integer> helplistr=list.subList(n, n);
        	List<Integer> helplistl=list.subList(0, n-1);
        	helplistr.addAll(helplistl);
        	r=Helper(helplistr.size(),m,helplistr);
        	return r;
    	}
    	
    	if(list.size()>2) {
    		List<Integer> helplistr=list.subList(flag, n);
            List<Integer> helplistl=list.subList(0, flag-1);
            helplistr.addAll(helplistl);
            r=Helper(helplistr.size(),m,helplistr);
            return r;
    	}
    	return r;
    }
    public static void main(String[] args) {
    	LastRemaining lr=new LastRemaining();
    	int r=lr.LastRemaining_Solution(5, 10);
    	System.out.println(r);
	}
}