题解 | 旺仔哥哥转圈圈

//算法练习No.12
//模拟+循环
//使用找循环节优化代码 用于跳出重复循环
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算出旺仔哥哥最后会站在哪位小朋友旁边
     * @param a int整型vector 第 i 个小朋友的数字是 a_i
     * @param m int整型 表示旺仔哥哥的移动次数
     * @return int整型
     */
    int stopAtWho(vector<int>& a, int m) {
        int n = a.size();
        if(n == 0) return 0;

        vector<int> history(n,-1);
        int current_idx = 0;

        for(long long i = 0;i<m;++i)
        {
            if(history[current_idx] != -1)
            {
                long long first_visit_step = history[current_idx];
                long long cycle_len = i - first_visit_step;//循环长度(数值循环)
                long long remaining_steps = m - i;//剩余未走步数

                long long real_steps_needed = remaining_steps % cycle_len;
                for(int j = 0;j<real_steps_needed;++j)
                {
                    long long steps = a[current_idx];
                    current_idx = (current_idx - (steps % n) + n) % n;
                }

                return current_idx + 1;
            }
            history[current_idx] = i;//记录当前位置是第i步来的

            long long steps = a[current_idx];
            current_idx = (current_idx - (steps % n) + n) % n;
        }
        return current_idx + 1;
        
        

        
    }
};