递枕头
难度:
标签:
题目描述
There are n people standing in a line labeled from 1 to n. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.
- For example, once the pillow reaches the
nthperson they pass it to then - 1thperson, then to then - 2thperson and so on.
Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.
Example 1:
Input: n = 4, time = 5 Output: 2 Explanation: People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2. Afer five seconds, the pillow is given to the 2nd person.
Example 2:
Input: n = 3, time = 2 Output: 3 Explanation: People pass the pillow in the following way: 1 -> 2 -> 3. Afer two seconds, the pillow is given to the 3rd person.
Constraints:
2 <= n <= 10001 <= time <= 1000
代码结果
运行时间: 14 ms, 内存: 16.0 MB
/*
* 题目思路：
* 使用 Java Stream 来实现相同的逻辑。
* 我们可以使用 IntStream 来模拟枕头的传递过程，并通过计算位置和方向的变化来确定最后的位置。
*/
import java.util.stream.IntStream;
public class PillowPassingStream {
public int findPersonWithPillow(int n, int time) {
int[] result = IntStream.range(0, time).boxed().reduce(new int[]{1, 1}, (acc, i) -> {
int pos = acc[0];
int dir = acc[1];
pos += dir;
if (pos == n || pos == 1) {
dir = -dir;
}
return new int[]{pos, dir};
}, (a, b) -> b);
return result[0];
}
}解释
方法:
该题解采用模拟整个过程的方式来解决问题。初始化时，第一个人拿着枕头（i = 1），且枕头的传递方向为正向（flag = 1）。在每个时间单位中，根据当前的方向移动枕头到下一个人。当枕头到达队首或队尾时，枕头的传递方向将反转（通过将flag乘以-1实现）。这个过程持续进行直到达到指定的时间。最后返回枕头所在的人的编号。
时间复杂度:
O(time)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中提到的模拟方法是否是解决这个问题的最有效方法，还是存在更优的算法？
▷🦆
当枕头到达队尾或队首时，你是如何确保方向转换的逻辑正确无误的？具体是通过哪些条件判断实现的？
▷🦆
如果n的值非常大，但time相对较小，模拟方法的效率如何？是否有其他方法可以优化这种情况下的运算效率？
▷🦆
题解中提到使用flag变量来控制枕头传递的方向，这种方式是否最为直观？还有没有其他可能的实现方式？
▷