LeetCode 2582. 递枕头：数学规律与 O(1) 解法

题目描述

有 n 个人站成一排，编号从 1 到 n。枕头最初在第 1 个人手里。每一秒，枕头会传递给相邻的人。如果枕头到达了队首（第 1 个人）或队尾（第 n 个人），传递方向就会反转。给你 n 和 time，返回 time 秒后枕头在谁手里。

示例：

  • 输入：n = 4, time = 9，输出：4
  • 输入：n = 3, time = 2，输出：3

解题思路

直接模拟传递过程当然可以，但 time 可能很大，模拟会超时。观察传递规律，可以发现它是一个周期性的往返运动。

以 n = 4 为例，枕头的位置随时间变化如下：

1
2
时间: 0  1  2  3  4  5  6  7  8  9  10 11 12
位置: 1  2  3  4  3  2  1  2  3  4  3  2  1

可以看到，位置序列在 1 和 4 处会发生“折返”。如果去掉折返时重复的端点，可以把序列拉直成一个更规整的周期：

1
1 -> 2 -> 3 -> 4 -> 4 -> 3 -> 2 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 3 -> 2 -> 1

这样每个周期的长度是 2 * n？实际上，从 1 到 4 再回到 1 是一个完整的来回。原始来回包含 2 * (n - 1) + 1 = 2n - 1 个时间点。但为了用数学公式统一计算，我们把转折点（1 和 n）重复一次，使得每个“半周期”的长度为 n。

关键公式

  1. 计算需要多少个“半周期”
    每个半周期长度是 n - 1（因为从 1 到 n 需要 n - 1 步）。
    设 ch 为经过的完整半周期数（即从一端走到另一端的次数），则：

    1
    ch = time / (n - 1)

    如果 time 不能整除 n - 1，说明还需要再走一次半周期才能覆盖 time，所以向上取整：

    1
    2
    3
    4
    if not ch.is_integer():
        ch = int(ch) + 1
    else:
        ch = int(ch)

  2. 计算去重后序列的总长度
    每经过一个半周期，序列中会增加 n 个点，但相邻半周期之间会重复一个端点，所以总长度为：

    1
    arry = ch * n - (ch - 1)

  3. 根据 ch 的奇偶性确定最终位置

    • 如果 ch 是偶数，说明当前正处在“从 n 返回 1”的方向上，位置为 arry - time。
    • 如果 ch 是奇数，说明当前正处在“从 1 走向 n”的方向上，位置为 n - (arry - time) + 1。

边界情况

当 time < n 时，枕头还没有到达队尾，直接返回 time + 1 即可，因为初始位置是 1，第 time 秒在 time + 1。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        if time < n:
            return time + 1
        else:
            # 计算需要的半周期数
            ch = time / (n - 1)
            if not ch.is_integer():
                ch = int(ch) + 1
            else:
                ch = int(ch)

            # 去重后序列的总长度
            arry = ch * n - (ch - 1)

            # 根据半周期数的奇偶性返回位置
            if ch % 2 == 0:
                return arry - time
            else:
                return n - (arry - time) + 1

示例解析：n = 4, time = 9

  • time = 9，n = 4，不满足 time < n，进入 else。
  • ch = 9 / (4 - 1) = 9 / 3 = 3.0，是整数，所以 ch = 3。
  • arry = 3 * 4 - (3 - 1) = 12 - 2 = 10。
  • ch 是奇数（3），走 else 分支：return 4 - (10 - 9) + 1 = 4 - 1 + 1 = 4。
  • 结果正确，第 9 秒枕头在第 4 个人手里。

复杂度分析

  • 时间复杂度：O(1)，只进行了常数次算术运算。
  • 空间复杂度：O(1)，仅使用了几个变量。

总结

这道题的核心是找到传递过程的周期性规律。通过将往返运动“拉直”，并用数学公式计算经过的半周期数，可以避免模拟整个传递过程，实现 O(1) 的高效解法。需要注意边界条件（如 time < n）和浮点数除法的取整处理。

希望这篇题解对你有帮助！如果觉得有用，欢迎点赞收藏。