queue队列算法模板-附LeetCode每日一题题解:1823. 找出游戏的获胜者-题解-python && C++源代码

简介: queue队列算法模板-附LeetCode每日一题题解:1823. 找出游戏的获胜者-题解-python && C++源代码

1823. 找出游戏的获胜者


难度中等66收藏分享切换为英文接收动态反馈


共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n ,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。


游戏遵循如下规则:


从第 1 名小伙伴所在位置 开始 。

沿着顺时针方向数 k 名小伙伴,计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数,一些小伙伴可能会被数过不止一次。

你数到的最后一名小伙伴需要离开圈子,并视作输掉游戏。

如果圈子中仍然有不止一名小伙伴,从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始,回到步骤 2 继续执行。

否则,圈子中最后一名小伙伴赢得游戏。

给你参与游戏的小伙伴总数 n ,和一个整数 k ,返回游戏的获胜者。


示例 1:


image.png


输入:n = 5, k = 2

输出:3

解释:游戏运行步骤如下:

1) 从小伙伴 1 开始。

2) 顺时针数 2 名小伙伴,也就是小伙伴 1 和 2 。

3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。

4) 顺时针数 2 名小伙伴,也就是小伙伴 3 和 4 。

5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。

6) 顺时针数 2 名小伙伴,也就是小伙伴 5 和 1 。

7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。

8) 顺时针数 2 名小伙伴,也就是小伙伴 3 和 5 。

9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。

示例 2:


输入:n = 6, k = 5

输出:1

解释:小伙伴离开圈子的顺序:5、4、6、2、3 。小伙伴 1 是游戏的获胜者。


解题思路:

队列真是个神奇的数据结构,个人认为用起来要比list列表舒服多了,至少这可以两边互相弹出插入,而且速度要比列表快

在这道题中,我们首先构造一个队列,将1到n塞进去,然后我们例如队列可以左右互插的特点,因为每次要把第k个数搞出去,

所以我们每次只需要将前k-1个数放到队列最后,然后第k个数就变成了在队列首位,弹出即可,反复进行即可。


python代码:

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        ans = deque(range(1 , n+1))#建立 0 到 n+1的队列
        while len(ans)>1: #等数组的个数到一个的时候,就跳出循环,输出即可
            for i in range(k-1):#将队列的前k-1位都放到队列最后
                ans.append(ans.popleft())#将第K位提到首位
            ans.popleft()#然后弹出首位
        return ans[0]#返回首位即是留下的值

C++代码:

class Solution {
public:
    int findTheWinner(int n, int k) {
        queue<int> ans;
        for(int i=1; i<n+1; i++) ans.emplace(i); //建立 0 到 n+1的队列
        while(ans.size()>1){  //等数组的个数到一个的时候,就跳出循环,输出即可
            for (int i=0; i<k-1; i++){ //将队列的前k-1位都放到队列最后
                ans.emplace(ans.front()); //将第K位提到首位
                ans.pop(); 
            }
            ans.pop(); //然后弹出首位
        }
        return ans.front();//返回首位即是留下的值
    }
};
相关文章
|
7天前
|
编解码 算法 Linux
Linux平台下RTSP|RTMP播放器如何跟python交互投递RGB数据供视觉算法分析
在对接Linux平台的RTSP播放模块时,需将播放数据同时提供给Python进行视觉算法分析。技术实现上,可在播放时通过回调函数获取视频帧数据,并以RGB32格式输出。利用`SetVideoFrameCallBackV2`接口设定缩放后的视频帧回调,以满足算法所需的分辨率。回调函数中,每收到一帧数据即保存为bitmap文件。Python端只需读取指定文件夹中的bitmap文件,即可进行视频数据的分析处理。此方案简单有效,但应注意控制输出的bitmap文件数量以避免内存占用过高。
|
6天前
|
编译器 C++
【C++】模板初级
【C++】模板初级
|
8天前
|
JSON 算法 API
京东以图搜图功能API接口调用算法源码python
京东图搜接口是一款强大工具,通过上传图片即可搜索京东平台上的商品。适合电商平台、比价应用及需商品识别服务的场景。使用前需了解接口功能并注册开发者账号获取Key和Secret;准备好图片的Base64编码和AppKey;生成安全签名后,利用HTTP客户端发送POST请求至接口URL;最后解析JSON响应数据以获取商品信息。
|
11天前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
27 6
|
6天前
|
安全 编译器 C++
【C++】模板进阶
【C++】模板进阶
|
7天前
|
算法 Python
python多继承的3C算法是什么?怎么用?
有很多地方都说python多继承的继承顺序,是按照深度遍历的方式,其实python多继承顺序的算法,不是严格意义上的深度遍历,而是基于深度遍历基础上优化出一种叫3C算法
|
8天前
|
数据采集 机器学习/深度学习 算法
【python】python客户信息审计风险决策树算法分类预测(源码+数据集+论文)【独一无二】
【python】python客户信息审计风险决策树算法分类预测(源码+数据集+论文)【独一无二】
|
11天前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
25 1
|
11天前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
22 1
|
4天前
|
算法
互动游戏解决遇到问题之基于射线投射寻路算法的问题如何解决
互动游戏解决遇到问题之基于射线投射寻路算法的问题如何解决