Jocephus杀人问题

说明

有一群俘虏n个人，但是粮食只够一个人吃，这群俘虏只能剩下一个人，其他人都得死。把刀给第1个人，第1个人杀掉第2个人，然后把刀给第3个人，第3个人杀掉第4个人，然后把刀给第5个人…最后只剩1个人。

如上图所示：1杀2，1把刀给3，3杀4，3把刀给5，5杀6，5把刀给7，7杀8，7把刀给9，现在只剩下1、3、5、7、9

根据上面地规则继续，最后只剩下3存活

那么给定一个列表，根据Jocephus杀人规则得到最后一个幸存者。

问题分析

代码

/**
 * Jocephus杀人问题
 * @author jeffrey
 * @date 3/25/20 8:58 AM
 */
public class JocephusKill {
    public static void main(String[] args) {
        List<String> humans = new ArrayList<>();
        humans.add("张1");
        humans.add("张2");
        humans.add("张3");
        humans.add("张4");
        humans.add("张5");
        humans.add("张6");
        humans.add("张7");
        humans.add("张8");
        humans.add("张9");
        System.out.println(getLast(humans));
    }
    public static String getLast(List<String> humans) {
        Queue<String> queue = new LinkedBlockingQueue<>(humans.size());
        queue.addAll(humans);
        while (queue.size() > 1) {
            String killer = queue.poll();
            String killed = queue.poll();
            queue.add(killer);
        }
        return queue.poll();
    }
}