【每日一题Day338】LC2582递枕头 | 模拟+数学

递枕头【LC2582】

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

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

• 例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。

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

• 思路

  每一轮次（从1到n或者从n到1）需要$n-1$秒，求出 time 秒可以完成的完整轮次$time/(n-1)$，剩余时间为$time\%(n-1)$

  • 若$time/(n-1)$为偶数，那么下一轮次从1出发，返回$1+time\%(n-1)$
  • 若$time/(n-1)$为奇数，那么下一轮次从n出发，返回$n-time\%(n-1)$

• 实现

  class Solution {
      public int passThePillow(int n, int time) {
          int cur = time / (n - 1);
          if (cur % 2 == 0){
              return 1 + time % (n - 1);
          }else{
              return n - time % (n - 1);
          }
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

  • 复杂度
    • 时间复杂度：$\mathcal{O}(1)$
    • 空间复杂度：$\mathcal{O}(1)$