跳转至

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

题目描述

给你两个 正整数 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

 

注意：此问题与 2582. 递枕头 一致。

解法

方法一：数学

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

接下来我们判断当前的轮数 \(k\)：

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

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

1
2
3
4
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

1
2
3
4
5
6
7
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;
    }
}

1
2
3
4
5
6
7
8
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;
    }
};

1
2
3
4
5
6
7
8
func numberOfChild(n int, k int) int {
    mod := k % (n - 1)
    k /= (n - 1)
    if k%2 == 1 {
        return n - mod - 1
    }
    return mod
}

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

评论