剑指offer-46-孩子们的游戏

思路

• 模拟，用队列模拟
• 递归, 考虑数组实现循环队列， f(n, m) = (m % n + x) % n = (m + x) % n

代码

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<n;i++){
            queue.add(i);
        }
        while(queue.size()>1){
            int cnt=0;
            while(cnt<m-1 && queue.size()>1){
                queue.add(queue.poll());
                cnt++;
            }
            if(cnt==m-1 &&queue.size()>1){
                queue.poll();
            }
        }
        return queue.size()==1?queue.poll():-1;
    }
}