题目链接

旺仔哥哥转圈圈

题目描述

这是一个函数实现题。有 n 个小朋友（编号 1 到 n）围成一圈，每个小朋友的衣服上有一个数字，记录在数组 a 中（a[i] 是第 i+1 个小朋友的数字）。

旺仔哥哥从 1 号小朋友旁边开始，总共移动 m 次。每次移动的规则如下：

  1. 查看当前所在位置小朋友衣服上的数字，设为 k。
  2. 逆时针走过 k 个小朋友，到达新的位置。

你需要实现 stopAtWho 函数，计算并返回经过 m 次移动后，旺仔哥哥最终所在位置的小朋友的编号。

示例:

  • 输入: a = [2, 1, 4, 5, 2, 3], m = 3
  • 你的函数应返回: 5
  • 说明:
    1. 开始在 1 号位。1 号数字是 2。逆时针走 2 位，到达 5 号位。
    2. 当前在 5 号位。5 号数字是 2。逆时针走 2 位，到达 3 号位。
    3. 当前在 3 号位。3 号数字是 4。逆时针走 4 位，到达 5 号位。
    4. 移动结束，最终在 5 号位。

解题思路

本题是一个纯粹的模拟题，我们只需要按照题目描述的规则，一步一步地模拟旺仔哥哥的移动过程即可。核心在于处理环形结构中的索引计算。

  1. 状态表示与索引:

    • 小朋友总数 n 就是数组 a 的长度。
    • 小朋友编号是 1-based (1 to n)，而数组索引是 0-based (0 to n-1)。我们需要在它们之间进行转换。一个小朋友的编号为 p，对应的数组索引是 p-1。
    • 我们可以用一个变量 current_idx 来表示旺仔哥哥当前位置的 0-based 索引。初始时，他在 1 号小朋友旁边，所以 current_idx 初始化为 0。

  2. 模拟移动:

    • 我们需要一个循环，执行 m 次，代表 m 次移动。
    • 在每次循环内部，我们执行一次移动操作。

  3. 计算新位置 (核心):

    • 获取步数: 首先，根据当前位置 current_idx，从数组 a 中获取步数：steps = a[current_idx]。
    • 环形移动: 由于小朋友是围成一圈的，移动 steps 步和移动 steps % n 步的效果是一样的。为了防止 steps 过大，我们先取模：effective_steps = steps % n。
    • 逆时针计算: 逆时针移动相当于在数组中向左移动，即索引减小。new_idx = current_idx - effective_steps。
    • 处理负数索引 (回绕): current_idx - effective_steps 的结果可能是负数。例如，在 6 个小朋友的圈中，从索引 0 逆时针移动 2 步 (0 - 2 = -2)，应该到达索引 4。为了正确处理这种情况，我们使用一个健壮的模运算技巧： new_idx = (current_idx - effective_steps + n) % n
      • 先加上 n 可以保证即使 current_idx - effective_steps 为负，结果也会变为正数。
      • 最后对 n 取模，将索引规范到 [0, n-1] 的范围内。

  4. 最终结果:

    • 循环 m 次后，我们得到的 current_idx 就是最终位置的 0-based 索引。
    • 将其转换回 1-based 的小朋友编号 current_idx + 1，并作为函数结果返回。

代码

注意：以下是你需要提交的全部内容，即在牛客网给定的模板中填写的代码。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算出旺仔哥哥最后会站在哪位小朋友旁边
     * @param a int整型vector 第 i 个小朋友的数字是 a_i
     * @param m int整型 表示旺仔哥哥的移动次数
     * @return int整型
     */
    int stopAtWho(std::vector<int>& a, int m) {
        int n = a.size();
        if (n == 0) {
            return 0; // 或者根据题意处理异常情况
        }
        
        long long current_idx = 0; // 使用 long long 防止中间计算溢出，虽然本题int足够
        
        for (int i = 0; i < m; ++i) {
            long long steps = a[current_idx];
            // 逆时针移动，即索引减小。加上n再取模以处理负数情况。
            current_idx = (current_idx - (steps % n) + n) % n;
        }
        
        return current_idx + 1; // 返回1-based的编号
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算出旺仔哥哥最后会站在哪位小朋友旁边
     * @param a int整型一维数组 第 i 个小朋友的数字是 a_i
     * @param m int整型 表示旺仔哥哥的移动次数
     * @return int整型
     */
    public int stopAtWho(int[] a, int m) {
        int n = a.length;
        if (n == 0) {
            return 0; // 或者根据题意处理异常
        }
        
        // Java的%对于负数结果也是负数，所以需要特殊处理
        // currentIdx - steps % n 的结果可能是负数
        int currentIdx = 0;
        
        for (int i = 0; i < m; i++) {
            int steps = a[currentIdx];
            int effectiveSteps = steps % n;
            
            // (currentIdx - effectiveSteps % n + n) % n 是一种健壮的写法
            currentIdx = (currentIdx - effectiveSteps + n) % n;
        }
        
        return currentIdx + 1; // 转换为1-based编号
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算出旺仔哥哥最后会站在哪位小朋友旁边
# @param a int整型一维数组 第 i 个小朋友的数字是 a_i
# @param m int整型 表示旺仔哥哥的移动次数
# @return int整型
#
class Solution:
    def stopAtWho(self, a: List[int], m: int) -> int:
        n = len(a)
        if n == 0:
            return 0 # 题目保证 n >= 1，此为防御性代码

        current_idx = 0
        for _ in range(m):
            steps = a[current_idx]
            # Python的 % 运算符对负数处理得很优雅，能直接得到正确结果
            # -1 % 6 = 5, -2 % 6 = 4 etc.
            current_idx = (current_idx - steps) % n
        
        return current_idx + 1 # 转换为1-based编号

算法及复杂度

  • 算法: 循环模拟。
  • 时间复杂度: ，其中 是移动的总次数。我们进行 M 次循环，每次循环内部的操作（取数、模运算、赋值）都是 的。
  • 空间复杂度: 。我们只使用了常数级别的额外空间来存储当前位置、循环变量等。