击鼓传花

题目描述

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

当游戏开始时，会每秒种击一次鼓。

排在队首的第一个人拿着花。每击一次鼓，持花人会将花传递给队伍中的下一个人。

一旦花到达队首或队尾，传递方向就会改变，队伍会将花继续沿相反方向传递。

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

给你两个正整数 `n` 和 `s` ，返回 `s` 秒后拿着花的人的编号。

示例：

# 示例 1：
# 输入：n = 4, s = 5
# 输出：2
# 解释：队伍中花的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
# 5 秒后，花传递到第 2 个人手中。

# 示例 2：
# 输入：n = 3, s = 2
# 输出：3
# 解释：队伍中花的传递情况为：1 -> 2 -> 3 。
# 2 秒后，花传递到第 3 个人手中。

解题思路

理解传递过程。
确定实际步数。
判断传递方向。
处理反向传递。

作答模板

python 模板

def pass_the_flower(n, s):
    """
    中间是你要实现的代码
    """
    return result

java 模板

class Solution {
    public Node passTheFlower(int n, int s) {
        // 中间是你要实现的代码
        return result;
    }
}

参考答案

python

def pass_the_flower(n, s):
        # 1. 计算花传递的整个周期是多少
        # 从第一个花到最后一个花需要的 n - 1 步
        # 从最后一个花到最前面的一个花需要 n -1 步
        # 一个整体的周期他的步数是 ： 正向周期 + 逆向周期 = （n-1）+（n-1） = 2 * （n-1） = 2n - 2
        idx = s % (2*n-2)

        # 2.通过判断idx 是否大于n，来判断此时是在正向周期还是逆向周期
        if idx < n:
            # 3. 是在正向周期，步数idx+1就是当前花传递的位置
            return idx + 1
        else:
            # 4. 我们是在反向周期，将其转换为正向周期的偏移步数，通过n-偏移步数，因为是逆向所以通过-1定位到当前拿花的人是谁
            return n - (idx%n) - 1

if __name__ == '__main__':
    print(pass_the_flower(4,5))
    print(pass_the_flower(3,2))

java

package 击鼓传花;
import java.util.Scanner;

class Solution {
    public int passTheFlower(int n, int s) {
        // 1.计算花的整体传递的周期
        int period = 2 * (n - 1);

        // 2.计算s秒后花的实际步数
        s %= period;

        // 3.判断s是否大于n
        if (s < n){
            // 4. 当前走的是正向的周期
            return s + 1;
        }else {
            // 5. 当前走的是逆向周期
            // 先通过 s % n 求出来当前在正向周期的偏移步数，因为是逆向：n - (s % n)，因为是逆向和步数原因：n - (s % n) -1
            return n - (s % n) -1;
        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 获取用户输入
        System.out.print("请输入队伍中人的数量 n：");
        int n = scanner.nextInt();
        System.out.print("请输入秒数 s：");
        int s = scanner.nextInt();

        // 创建 Solution 实例并调用 passTheFlower 方法
        Solution sol = new Solution();
        int result = sol.passTheFlower(n, s);

        // 输出结果
        System.out.println("在 " + s + " 秒后，拿着花的人的编号是：" + result);

        scanner.close();  // 关闭 Scanner
    }
}