【05-04】力扣每日一题

今天的每日一题就是模拟的思路，不过看到这个题感觉有数学的方法可解，果然有！

题目描述

题目分析

首先我们理解下题目的意思，题目的意思就是，有n个小伙伴围成一圈玩游戏，然后随便给一个数k，k的范围为[1,500]。然后从第一个小伙伴开始数，数到k的时候，那个小伙伴就出局了，接着从k+1个小伙伴开始数（从1开始数），然后数到k，数到k的小伙伴又出局了（我为什么要说又）。一直这样下去，直到最后一个剩下的小伙伴就是我们的winner。

既然如此，那一般的做法就是模拟这个过程嘛。我们可以使用循环链表来模拟这个过程，首先建立循环链表，然后从第一个开始数k个，有两个指针，一个指向当前数到的节点，一个指向当前数到结点的前一个。当数到k的时候，我们就删除这个结点，删除操作如下。然后循环结束的条件就是当前结点的下一个结点指向自己（也就是循环链表中只有一个节点），游戏结束，返回这个结点的值。

pre 和 cur
pre代表前一个结点 cur代表当前结点
pre->next = cur->next;// 删除当前结点
cur = pre->next;//重新设置cur

当然这道题其实还有数学解法，数学解法更为惊艳，首先给出公式，其中$f(n,k)$表示n个人，每次数到k那个人就淘汰，最后赢家的下标。那么n个人数到k赢家的下标与n-1个人数到k赢家的下标有着如下的递推关系。至于这个公式的证明，我们可以参考这个博客约瑟夫环。这个博客写得很清楚明白，所以我不做多说。
$$
f(n,k) = (f(n-1,k)+k) % n
$$

代码实现

循环链表解法：

class Solution {
public:
    int findTheWinner(int n, int k) {
        // 首先初始化链表
        ListNode* head = new ListNode(1,NULL);
        ListNode* root = head;
        for(int i = 2;i<=n;i++){
            ListNode* tmp = new ListNode(i,NULL);
            root->next = tmp;
            root = root->next;
        }
        // 建立循环链表
        root->next = head;
        ListNode* pre = root;
        ListNode* cur = head;
        while(cur->next!=cur){
            int i = 1;
            while(i<k){
                // 保留前一项
                pre = cur;
                // 往后数k个
                cur = cur->next;
                i++;
            }
            // skip last one
            pre->next = cur->next;
            cur = pre->next;
        }
        return cur->val;
    }
};

数学解法：

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