Question

2582. 递枕头

English Version

题目描述

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

解法

方法一：模拟

我们可以模拟枕头传递的过程，每次传递枕头时，如果枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

时间复杂度 $O(time)$，空间复杂度 $O(1)$。其中 $time$ 为给定的时间。

class Solution:
  def passThePillow(self, n: int, time: int) -> int:
    ans = k = 1
    for _ in range(time):
      ans += k
      if ans == 1 or ans == n:
        k *= -1
    return ans

class Solution {
  public int passThePillow(int n, int time) {
    int ans = 1, k = 1;
    while (time-- > 0) {
      ans += k;
      if (ans == 1 || ans == n) {
        k *= -1;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int passThePillow(int n, int time) {
    int ans = 1, k = 1;
    while (time--) {
      ans += k;
      if (ans == 1 || ans == n) {
        k *= -1;
      }
    }
    return ans;
  }
};

func passThePillow(n int, time int) int {
  ans, k := 1, 1
  for ; time > 0; time-- {
    ans += k
    if ans == 1 || ans == n {
      k *= -1
    }
  }
  return ans
}

function passThePillow(n: number, time: number): number {
  let ans = 1,
    k = 1;
  while (time-- > 0) {
    ans += k;
    if (ans === 1 || ans === n) {
      k *= -1;
    }
  }
  return ans;
}

impl Solution {
  pub fn pass_the_pillow(n: i32, time: i32) -> i32 {
    let mut ans = 1;
    let mut k = 1;

    for i in 1..=time {
      ans += k;

      if ans == 1 || ans == n {
        k *= -1;
      }
    }

    ans
  }
}

方法二：数学

我们注意到，每一轮有 $n - 1$ 次传递，因此我们可以将 $time$ 除以 $n - 1$ 得到枕头传递的轮数 $k$，然后再将 $time$ 对 $n - 1$ 取余得到枕头在当前轮的剩余传递次数 $mod$。

接下来我们判断当前的轮数 $k$：

• 如果 $k$ 为奇数，那么枕头当前的传递方向是从队尾到队首，因此枕头会传递到编号为 $n - mod$ 的人手中；
• 如果 $k$ 为偶数，那么枕头当前的传递方向是从队首到队尾，因此枕头会传递到编号为 $mod + 1$ 的人手中。

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

class Solution:
  def passThePillow(self, n: int, time: int) -> int:
    k, mod = divmod(time, n - 1)
    return n - mod if k & 1 else mod + 1

class Solution {
  public int passThePillow(int n, int time) {
    int k = time / (n - 1);
    int mod = time % (n - 1);
    return (k & 1) == 1 ? n - mod : mod + 1;
  }
}

class Solution {
public:
  int passThePillow(int n, int time) {
    int k = time / (n - 1);
    int mod = time % (n - 1);
    return k & 1 ? n - mod : mod + 1;
  }
};

func passThePillow(n int, time int) int {
  k, mod := time/(n-1), time%(n-1)
  if k&1 == 1 {
    return n - mod
  }
  return mod + 1
}

function passThePillow(n: number, time: number): number {
  const k = time / (n - 1);
  const mod = time % (n - 1);
  return (k & 1) == 1 ? n - mod : mod + 1;
}

impl Solution {
  pub fn pass_the_pillow(n: i32, time: i32) -> i32 {
    let mut k = time / (n - 1);
    let mut _mod = time % (n - 1);

    if (k & 1) == 1 {
      return n - _mod;
    }

    _mod + 1
  }
}