【LetMeFly】2582.递枕头：清晰的话讲述 O(1)的时间算法

力扣题目链接：https://leetcode.cn/problems/pass-the-pillow/

n 个人站成一排，按从 1 到 n 编号。

最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

• 例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 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

方法一：计算

n个人传递枕头，从左到右需要传递$n-1$次。同理，从右到左也需要传$n-1$次。也就是说，$2\times (n-1)$次一循环。

因此，$time$直接模上个$2\times (n-1)$即等效于单轮传递的结果。

• 如果$time\le n-1$，则说明是在往右传。传$0$次处于$1$，传$1$次处于$2$，…，传$time$次处于$time+1$。

• 否则，说明是在往左传。往左传了$time-(n-1)$次。往左传$0$次处于$n$，往左传$1$次处于$n-1$，…，往左传$time-(n-1)$次处于$n-(time-(n-1))=2\ast n-time-1$。

• 时间复杂度$O(1)$

• 空间复杂度$O(1)$

AC代码

C++

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

Python

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

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133294825