Easy

题目描述

有 n 个人站成一排，标号从 1 到 n。最初，排在第一位的人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队列中的下一个人。一旦枕头到达队列的末端，传递方向就会改变，人们继续沿相反方向传递枕头。

例如，一旦枕头到达第 n 个人，他们会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。

给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。

示例 1：

输入: n = 4, time = 5
输出: 2
解释: 人们按以下方式传递枕头: 1 -> 2 -> 3 -> 4 -> 3 -> 2。
5秒后，第2个人拿着枕头。

示例 2：

输入: n = 3, time = 2
输出: 3
解释: 人们按以下方式传递枕头: 1 -> 2 -> 3。
2秒后，第3个人拿着枕头。

约束条件：

  • 2 <= n <= 1000
  • 1 <= time <= 1000

解题思路

这道题有两种主要解法：

解法一：模拟法 按照题意直接模拟传递过程。维护当前位置和传递方向，每次时间+1就更新位置。当到达边界时改变方向。这种方法直观易懂，但时间复杂度为O(time)。

解法二：数学法（推荐） 观察传递规律可以发现，枕头的传递是周期性的。从位置1到位置n再回到位置1构成一个完整周期，长度为2*(n-1)。

具体分析：

  • 第一段：1 -> 2 -> … -> n，需要n-1秒
  • 第二段：n -> n-1 -> … -> 1，需要n-1秒
  • 总周期长度：2*(n-1)秒

通过取余运算确定在周期内的位置：

  • 如果余数在[0, n-1]范围内，说明在正向传递阶段，位置为余数+1
  • 如果余数在[n, 2*(n-1)-1]范围内，说明在反向传递阶段，位置为n-(余数-(n-1))

数学解法的时间复杂度为O(1)，更加高效。

代码实现

class Solution {
public:
    int passThePillow(int n, int time) {
        int cycle = 2 * (n - 1);
        int pos = time % cycle;
        
        if (pos <= n - 1) {
            return pos + 1;
        } else {
            return n - (pos - (n - 1));
        }
    }
};

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        cycle = 2 * (n - 1)
        pos = time % cycle
        
        if pos <= n - 1:
            return pos + 1
        else:
            return n - (pos - (n - 1))

public class Solution {
    public int PassThePillow(int n, int time) {
        int cycle = 2 * (n - 1);
        int pos = time % cycle;
        
        if (pos <= n - 1) {
            return pos + 1;
        } else {
            return n - (pos - (n - 1));
        }
    }
}

/**
 * @param {number} n
 * @param {number} time
 * @return {number}
 */
var passThePillow = function(n, time) {
    const cycle = 2 * (n - 1);
    const pos = time % cycle;
    
    if (pos <= n - 1) {
        return pos + 1;
    } else {
        return n - (pos - (n - 1));
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
数学法O(1)O(1)
模拟法O(time)O(1)

相关题目