大连网站建设设计,360网站收录提交,西安网站建设陕icp,天津非常好的网站建设目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
n 个朋友… 目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 描述
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 解题思路
* 2682. 找出转圈游戏输家
* 解题思路
* 每次求新的传球位置先求出下一个位置然后和n求余就可以了。公式为(lastPosition index * k) % n;
* 把每一个位置都加到set中然后遍历1到n的位置如果在set中则不再set中则说明是没有接到过球的就加入到answer中。
代码
class Solution2682
{
public:vectorint circularGameLosers(int n, int k){setint set;int lastPosition 0;int index 1;set.insert(0);while (true){int position (lastPosition index * k) % n;if (set.find(position) ! set.end()){break;}index;set.insert(position);lastPosition position;}vectorint answer;for (int i 1; i n; i){if (set.find(i - 1) ! set.end()){continue;}answer.push_back(i);}return answer;}
};
