益阳网站建设公司有哪些,手机网站演示,做同城购物网站,官网建设的意义【LetMeFly】2682.找出转圈游戏输家
力扣题目链接#xff1a;https://leetcode.cn/problems/find-the-losers-of-the-circular-game/
n 个朋友在玩游戏。这些朋友坐成一个圈#xff0c;按 顺时针方向 从 1 到 n 编号。从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i …【LetMeFly】2682.找出转圈游戏输家
力扣题目链接https://leetcode.cn/problems/find-the-losers-of-the-circular-game/
n 个朋友在玩游戏。这些朋友坐成一个圈按 顺时针方向 从 1 到 n 编号。从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i 1) 个朋友的位置1 i n而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。
游戏规则如下
第 1 个朋友接球。
接着第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。然后接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。接着接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友以此类推。
换句话说在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。
当某个朋友第 2 次接到球时游戏结束。
在整场游戏中没有接到过球的朋友是 输家 。
给你参与游戏的朋友数量 n 和一个整数 k 请按升序排列返回包含所有输家编号的数组 answer 作为答案。 示例 1
输入n 5, k 2
输出[4,5]
解释以下为游戏进行情况
1第 1 个朋友接球第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。
2第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。
3第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。
4第 3 个朋友接到两次球游戏结束。示例 2
输入n 4, k 4
输出[2,3,4]
解释以下为游戏进行情况
1第 1 个朋友接球第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。
2第 1 个朋友接到两次球游戏结束。 提示
1 k n 50
方法一模拟
开辟一个长度为 n n n的布尔类型的数组 v i s i t e d visited visited初始值全部为 0 0 0用来记录哪个小朋友拿到过球。
使用两个变量 w h o who who和 t h th th分别记录当前球在谁的手里、这是第几次传球。
当 v i s i t e d [ w h o ] visited[who] visited[who]为 f a l s e false false时不断更新 v i s i t e d visited visited、 w h o who who、 t h th th。
最终遍历一遍 v i s i t e d visited visited数组将没接到过球的娃子添加到答案数组中即可。
时间复杂度 O ( n ) O(n) O(n)每个人最多接到球 1 1 1次第二次还没接就退出循环了空间复杂度 O ( n ) O(n) O(n)
AC代码
C
class Solution {
public:vectorint circularGameLosers(int n, int k) {vectorbool visited(n);int who 0, th 0;while (!visited[who]) {visited[who] true;who (who th * k) % n;}vectorint ans;for (int i 0; i n; i) {if (!visited[i]) {ans.push_back(i 1);}}return ans;}
};Python
# from typing import Listclass Solution:def circularGameLosers(self, n: int, k: int) - List[int]:visited [False] * nwho, th 0, 0while not visited[who]:visited[who] Trueth 1who (who th * k) % nans []for i in range(n):if not visited[i]:ans.append(i 1)return ans同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/132311270
