n个朋友在玩游戏。这些朋友坐成一个圈,按顺时针方向1n编号。从第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

这个题目其实直接模拟游戏过程即可。主要可能每一次跳的 k * i需要关注下,并且还需要进行取余操作。

思路:

记录起始位置start,每一次的跳跃步长 step * k,其中step是第几次跳。然后记录遍历过的玩家数量cnt,用于后面答案数组的初始化长度 n – cnt,vis标记为是否遍历过的玩家。

ac code:

class Solution {public int[] circularGameLosers(int n, int k) {boolean[] vis = new boolean[n+1];int start = 1;int step = 0;int cnt = 0;while (!vis[(start + step * k) % n]) {vis[(start + step * k) % n] = true;start = start + step * k;step += 1;cnt += 1;}int[] ans = new int[n - cnt];int index = 0;for (int i=1;i<=n;i++) {if (!vis[i % n]) {ans[index++] = i;}}return ans;}}