给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= $nums.length$ <= $10^5$
• $-2^{31}$ <= nums[i] <= $2^{31}$ -1
• 0 <= k <= $10^5$

进阶：

尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

题解1 环状替换（学习思想）（空间O(1)）

class Solution {
public:void rotate(vector<int>& nums, int k) {const int s = nums.size();、// 先处理k（减少后面的不必要循环）k = k % s;// cylimit 就是为了保证能把元素全部遍历, 设最小遍历次数为N// N = as = bk (等式基于遍历经过的长度)-> N 应该是s, k的最小公倍数lcm(s, k)// lcm(s, k)/k = b 即遍历N次遍历过的元素总数目// cylimit = s / (1/k * lcm(s, k)) = sk / lcm(s,k) = gcd(s, k) 即s, k最大公倍数  int cylimit = gcd(k, s);for(int c = 0; c < cylimit; c++){// O(1)： 把每个能计算到的位置对应的原来的值放在[c]的位置int cur = c;do{// 新下标int newI = (cur+k) % s;// 每次都把改变的值放在[c]上swap(nums[newI], nums[c]);// 循环找下一个cur = newI;}while(cur != c); // %的关键：停止条件是回到起始位置}}
};

题解2 翻转数组（有意思好理解）（空间O(1)）

class Solution {
public:void reverse(vector<int>& nums, int start, int end){while(start < end){swap(nums[start], nums[end]);start ++;end --;}}void rotate(vector<int>& nums, int k) {const int s = nums.size();// 先处理k（减少后面的不必要循环）k = k % s;reverse(nums, 0, s-1);reverse(nums, 0, k-1);reverse(nums, k, s-1);}
};

题解3 空间O(N)秒答

class Solution {
public:void rotate(vector<int>& nums, int k) {const int s = nums.size();// 先处理k（减少后面的不必要循环）k = k % s;vector<int> newN(s, 0);for(int i = 0; i < s; i++){newN[(i+k)%s] = nums[i];}nums.assign(newN.begin(), newN.end());}
};