Find the Winner of the Circular Game
给一个数组, 是个圈, 里面有n个人编号为[1..n], 每次游戏踢出第k个, 问剩下的标号是多少
这个就模拟一下吧. 我用set标示被踢出的. 然后当set的大小等于n-1 剩下没标到的就是答案.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution { public int findTheWinner(int n, int k) { if(n == 1) return 1; LinkedList<Integer> list = new LinkedList<>(); Set<Integer> set = new HashSet<>(); for(int i = 1; i <= n; i++){ list.addLast(i); } for(int i = 1; i < n; i++){ for(int j = 0; j < k;){ if(!set.contains(list.peek())){ j++; } list.addLast(list.removeFirst()); } set.add(list.getLast()); if(set.size() == n - 1){ for(int f = 1; f <= n; f++){ if(!set.contains(f)) return f; } } } return -1; } } |