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

题目描述

  题目链接,1823. 找出游戏的获胜者。题目截图如下:

image-20220504115028616

题目分析

  首先我们理解下题目的意思,题目的意思就是,有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;
    }
};

总结

  道阻且长,行则将至!愿中国青年都摆脱冷气,只是向上走。不要听自暴自弃者的话。能做事的做事,能发声的发声。有一份光,发一份热。就令萤火一般,也可以在黑暗里发一点光。不必等候炬火。 —— 鲁迅

Q.E.D.


  Java后端开发工程师一名,北漂一族,欢迎大家前来交流