Easy

题目描述

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

最初，编号为 0 的小孩拿着球，传球方向是向右。每过一秒，拿着球的小孩会将球传给旁边的小孩。一旦球到达队伍的任何一端，即编号为 0 或 n - 1 的小孩，传球方向就会反转。

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

示例 1：

输入：n = 3, k = 5
输出：1
解释：
时间  | 小孩
  0   | [0, 1, 2]  // 小孩 0 拿球
  1   | [0, 1, 2]  // 小孩 1 拿球
  2   | [0, 1, 2]  // 小孩 2 拿球，到达右端，方向反转
  3   | [0, 1, 2]  // 小孩 1 拿球
  4   | [0, 1, 2]  // 小孩 0 拿球，到达左端，方向反转
  5   | [0, 1, 2]  // 小孩 1 拿球

示例 2：

输入：n = 5, k = 6
输出：2

示例 3：

输入：n = 4, k = 2
输出：2

约束条件：

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

提示：

  • 球会在 2 * (n - 1) 秒后回到小孩 0，一切都和时间 0 相同
  • 所以 k 的答案与 k % (2 * (n - 1)) 的答案相同

解题思路

解题思路

这道题可以用两种方法解决：

方法一：模拟法

直接模拟球的传递过程，维护当前持球小孩的位置和传球方向。每秒更新位置，当到达边界时反转方向。

方法二：数学公式法（推荐）

观察球的传递规律，发现每 2*(n-1) 秒为一个周期，球会回到初始状态。

传递序列为：0 → 1 → 2 → … → (n-1) → (n-2) → … → 1 → 0，总共 2*(n-1) 步完成一个周期。

对于任意时间 k，我们可以计算 k % (2*(n-1)) 来找到在周期内的位置。然后根据位置判断：

  • 如果在前半部分（0 到 n-1），位置就是 k
  • 如果在后半部分，位置是从 n-1 往回走，即 2*(n-1) - k

这种方法时间复杂度为 O(1)，比模拟法的 O(k) 更优。

代码实现

class Solution {
public:
    int numberOfChild(int n, int k) {
        int cycle = 2 * (n - 1);
        k %= cycle;
        
        if (k <= n - 1) {
            return k;
        } else {
            return cycle - k;
        }
    }
};

class Solution:
    def numberOfChild(self, n: int, k: int) -> int:
        cycle = 2 * (n - 1)
        k %= cycle
        
        if k <= n - 1:
            return k
        else:
            return cycle - k

public class Solution {
    public int NumberOfChild(int n, int k) {
        int cycle = 2 * (n - 1);
        k %= cycle;
        
        if (k <= n - 1) {
            return k;
        } else {
            return cycle - k;
        }
    }
}

var numberOfChild = function(n, k) {
    const cycle = 2 * (n - 1);
    k %= cycle;
    
    if (k <= n - 1) {
        return k;
    } else {
        return cycle - k;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数学公式法模拟法
时间复杂度O(1)O(k)
空间复杂度O(1)O(1)

相关题目