力扣每日一题2022-05-04中等题：找出游戏的获胜者

找出游戏的获胜者

• • 题目描述
  • 思路
  • • 数学
    • • C++实现
      • Java实现
      • Python实现

---

题目描述

找出游戏的获胜者

---

思路 数学

第一轮删掉第k个人，问题就变为n-1个人进行这个游戏。假设知道f(n-1, k)最终剩下的人的编号，由于删除第k个人，n-1个人的游戏从原来第k+1个人开始的，即原来的编号和新的编号有一个偏差k。以坐标从0到n-1来看，则有公式
f ( n , k ) = ( f ( n − 1 , k ) + k ) % n f(n, k) = (f(n-1, k) + k) \% n f(n,k)=(f(n−1,k)+k)%n
当只剩一个人，则必然存活。即f(1, k) = 0。从f(1, k)推导出f(2, k)直到f(n, k)即可。

C++实现

class Solution {
public:
    int findTheWinner(int n, int k) {
        if (n < 1 || k < 1) {
            return -1;
        }
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + k) % i;
        }
        return ans+1;
    }
};

Java实现

class Solution {
    public int findTheWinner(int n, int k) {
        if (n < 1 || k < 1) {
            return -1;
        }
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + k) % i;
        }
        return ans+1;
    }
}

Python实现

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        if n < 1 or k < 1:
            return -1
        ans = 0
        for i in range(2, n+1):
            ans = (ans + k) % i
        return ans+1