README.md

comments	difficulty	edit_url	rating	source	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3178.Find%20the%20Child%20Who%20Has%20the%20Ball%20After%20K%20Seconds/README.md	1255	第 401 场周赛 Q1	数学 模拟

3178. 找出 K 秒后拿着球的孩子

English Version

题目描述

给你两个 正整数 n 和 k。有 n 个编号从 0 到 n - 1 的孩子按顺序从左到右站成一队。

最初，编号为 0 的孩子拿着一个球，并且向右传球。每过一秒，拿着球的孩子就会将球传给他旁边的孩子。一旦球到达队列的 任一端 ，即编号为 0 的孩子或编号为 n - 1 的孩子处，传球方向就会 反转 。

返回 k 秒后接到球的孩子的编号。

 

示例 1：

输入：n = 3, k = 5

输出：1

解释：

经过的时间	孩子队列
0	[0, 1, 2]
1	[0, 1, 2]
2	[0, 1, 2]
3	[0, 1, 2]
4	[0, 1, 2]
5	[0, 1, 2]

示例 2：

输入：n = 5, k = 6

输出：2

解释：

经过的时间	孩子队列
0	[0, 1, 2, 3, 4]
1	[0, 1, 2, 3, 4]
2	[0, 1, 2, 3, 4]
3	[0, 1, 2, 3, 4]
4	[0, 1, 2, 3, 4]
5	[0, 1, 2, 3, 4]
6	[0, 1, 2, 3, 4]

示例 3：

输入：n = 4, k = 2

输出：2

解释：

经过的时间	孩子队列
0	[0, 1, 2, 3]
1	[0, 1, 2, 3]
2	[0, 1, 2, 3]

 

提示：

• 2 <= n <= 50
• 1 <= k <= 50

解法

方法一：数学

我们注意到，每一轮有 $n - 1$ 次传递，因此我们可以将 $k$ 对 $n - 1$ 取模，得到 $k$ 在当前轮的传递次数 $mod$，然后我们将 $k$ 除以 $n - 1$，得到当前的轮数 $k$。

接下来我们判断当前的轮数 $k$：

• 如果 $k$ 为奇数，那么当前的传递方向是从队尾到队首，因此会传递到编号为 $n - mod - 1$ 的人手中；
• 如果 $k$ 为偶数，那么当前的传递方向是从队首到队尾，因此会传递到编号为 $mod$ 的人手中。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

Python3

class Solution:
    def numberOfChild(self, n: int, k: int) -> int:
        k, mod = divmod(k, n - 1)
        return n - mod - 1 if k & 1 else mod

Java

class Solution {
    public int numberOfChild(int n, int k) {
        int mod = k % (n - 1);
        k /= (n - 1);
        return k % 2 == 1 ? n - mod - 1 : mod;
    }
}

C++

class Solution {
public:
    int numberOfChild(int n, int k) {
        int mod = k % (n - 1);
        k /= (n - 1);
        return k % 2 == 1 ? n - mod - 1 : mod;
    }
};

Go

func numberOfChild(n int, k int) int {
	mod := k % (n - 1)
	k /= (n - 1)
	if k%2 == 1 {
		return n - mod - 1
	}
	return mod
}

TypeScript

function numberOfChild(n: number, k: number): number {
    const mod = k % (n - 1);
    k = (k / (n - 1)) | 0;
    return k % 2 ? n - mod - 1 : mod;
}