Skip to content

Latest commit

 

History

History
273 lines (207 loc) · 5.77 KB

File metadata and controls

273 lines (207 loc) · 5.77 KB
comments difficulty edit_url rating source tags
true
简单
1278
第 335 场周赛 Q1
数学
模拟

English Version

题目描述

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

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

给你两个正整数 ntime ,返回 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

 

注意:本题与 3178.找出 K 秒后拿着球的孩子 一致。

解法

方法一:模拟

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

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

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}

Rust

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)$

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}

Rust

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
    }
}