class Solution {
public:
vector<int> circularGameLosers(int n, int k) {
}
};
2682. 找出转圈游戏输家
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原站题解
php 解法, 执行用时: 16 ms, 内存消耗: 18.8 MB, 提交时间: 2023-08-16 07:44:33
class Solution {
/**
* @param Integer $n
* @param Integer $k
* @return Integer[]
*/
function circularGameLosers($n, $k) {
$vis = array_fill(0, $n, false);
for ( $i=0, $d=$k; !$vis[$i]; $d += $k ) {
$vis[$i] = true;
$i = ($i + $d) % $n;
}
$ans = [];
foreach ( $vis as $i => $b ) {
if ( !$b ) $ans[] = $i+1;
}
return $ans;
}
}
php 解法, 执行用时: 12 ms, 内存消耗: 19.1 MB, 提交时间: 2023-08-16 07:43:12
class Solution {
/**
* @param Integer $n
* @param Integer $k
* @return Integer[]
*/
function circularGameLosers($n, $k) {
$vis = array_fill(0, $n, false);
$i = 0;
$d = $k;
while (!$vis[$i]) {
$vis[$i] = true;
$i = ($i + $d) % $n;
$d += $k;
}
$ans = [];
foreach ( $vis as $i => $b ) {
if ( !$b ) $ans[] = $i+1;
}
return $ans;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2023-05-22 14:35:52
func circularGameLosers(n int, k int) (ans []int) {
vis := make([]bool, n)
for i, d := 0, k; !vis[i]; d += k {
vis[i] = true
i = (i + d) % n
}
for i, b := range vis {
if !b {
ans = append(ans, i+1)
}
}
return
}
java 解法, 执行用时: 1 ms, 内存消耗: 42.7 MB, 提交时间: 2023-05-22 14:35:37
class Solution {
public int[] circularGameLosers(int n, int k) {
var vis = new boolean[n];
int m = n;
for (int i = 0, d = k; !vis[i]; d += k, m--) {
vis[i] = true;
i = (i + d) % n;
}
var ans = new int[m];
for (int i = 0, j = 0; i < n; i++)
if (!vis[i])
ans[j++] = i + 1;
return ans;
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-22 14:35:24
class Solution:
def circularGameLosers(self, n: int, k: int) -> List[int]:
vis = [False] * n
i, d = 0, k
while not vis[i]:
vis[i] = True
i = (i + d) % n
d += k
return [i for i, b in enumerate(vis, 1) if not b]