1823. 找出游戏的获胜者
来源：力扣（LeetCode）
链接：https://leetcode-/problems/find-the-winner-of-the-circular-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
经典的约瑟夫环问题
以前在课后练习题做过，当时想到能用的工具只有数组：用一个数组来模拟，每次将出局玩家对应的数组值置为-1，当所有玩家都被淘汰，游戏结束。
class Solution {public:int findTheWinner(int n, int k) {vector<int> arr(n, 0); // 设置一个标记数组，想要将出局的玩家标记int c = k; // 计数器c的初始值为kint i = 0; // i作为指针遍历数组while(n != 0){ // 玩家未全部出局if(arr[i] == 0 && c == 1){ // 该位置玩家出局arr[i] = -1; // 出局标记c = k; // 计数器重置n --; // 玩家数量减一if(n == 0) break; // 游戏结束i = (i + 1) % n; // 指针向后移动}else if(arr[i] == 0 && c != 1){ // 跳过该玩家c --;i = (i + 1) % n;}else i = (i + 1) % n; // 跳过出局玩家 }return i + 1; //最终胜利者}};
现在看起来似乎队列更加方便：
class Solution {public:int findTheWinner(int n, int k) {queue<int> q;for(int i = 1; i <= n ; i ++) q.push(i); // 所有玩家入队while(-- n){for(int j = 1; j < k ; j ++) { // k-1个玩家重新入队q.push(q.front());q.pop();}q.pop(); // 淘汰第k个玩家}return q.front(); //返回最后的胜者}};
