LeetCode-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

c语言实现

初步完成

int* circularGameLosers(int n, int k, int* returnSize){
    int i;
    int a[51]={0};//最多50人
    a[1]=1;//初始第一个人
    int next=1;//下一次是第几个人
    for(i=1;;i++)//循环直到第二个人接球结束
    {
        int lenth=i*k;//步长
        next+=lenth;//下一位接球者
        while(next>n)//超过人数最大限制时重新轮圈
        {
            next-=n;
        }
        a[next]++;//记录每人接球次数
        if(a[next]==2) break;//循环结束
    }
    int num=0;//计数
    for(i=1;i<=n;i++)
    {
        if(a[i]==0) num++;
    }
    *returnSize=num;
    int* answer=malloc(sizeof(int)*num);
    int j=0;
    for(i=1;i<=n;i++)
    {
        if(a[i]==0) answer[j++]=i;//确定返回的数组
    }
    return answer;
}

最终解法

int* circularGameLosers(int n, int k, int* returnSize){
    int i;
    bool visit[n];//是否接球
    memset(visit, 0, sizeof(visit));//使用memset初始化数组
    int next=0;//下一次是第几个人,从0开始
    for(i=k;!visit[next];i+=k)//循环直到第二个人接球结束
    {
        visit[next]=true;
        next=(next+i)%n;//使用取余简化解法,无需循环
    }
    int* answer=malloc(sizeof(int)*n);
    int j=0;
    for(i=0;i<n;i++)
    {
        if(!visit[i]) answer[j++]=i+1;//数组下标从0开始，所以需要+1
    }
    *returnSize=j;//j即为数组大小
    return answer;
}