[LeetCode 189] 轮转数组
题目描述：
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
范围：
1 ≤ n u m s . l e n g t h ≤ 105 1 \le nums.length \le 105 1≤nums.length≤105
− 2 31 ≤ n u m s [ i ] ≤ 2 31 − 1 -2^{31} \le nums[i] \le 2^{31} - 1 −231≤nums[i]≤231−1
0 ≤ k ≤ 1 0 5 0 \le k \le 10^5 0≤k≤105
思路：
1. 暴力new数组存储
void rotate(vector<int>& nums, int k) {size_tn = nums.size();vector<int> temp(n, 0);for(size_t i = 0; i < nums.size(); ++ i)temp[(i + k) % n] = nums[i];nums = temp;return ;}
2. 数组翻转 & 双指针
这边双指针指的是如果要自己写 r e v e r s e reverse reverse 的话。
（思路copy官方题解，but 王道考研里遇到过，很简单的逻辑）
该方法基于如下的事实：当我们将数组的元素向右移动 k k k 次后，尾部 k m o d n k\ mod\ n k mod n 个元素会移动至数组头部，其余元素向后移动 k m o d n k\ mod\ n k mod n 个位置。
该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 k m o d n k\ mod\ n k mod n 个元素就被移至数组头部，然后我们再翻转 [ 0 , k m o d n − 1 ] [0,k\ mod\ n−1] [0,k mod n−1] 区间的元素和 [ k m o d n , n − 1 ] [k\ mod\ n,n−1] [k mod n,n−1] 区间的元素即能得到最后的答案。
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) {k %= nums.size();Reverse(nums, 0, nums.size() - 1);Reverse(nums, 0, k - 1);Reverse(nums, k, nums.size() - 1);/**or use stl reversereverse(nums.begin(), nums.end());reverse(nums.begin(), nums.begin() + k);reverse(nums.begin() + k, nums,end());**/}
3. 原地轮转替换
最优但不好理解，umm maybe尝试群论/数论可以理解
（退步太多，思维缓慢，重新刷题，勉励自己）
两篇文章可帮助理解：blog 1，blog 2
void rotate(vector<int>& nums, int k) {k %= nums.size();int n = nums.size();int cnt = gcd(n, k);for(int i = 0; i < cnt; ++ i) {int j = i;int pre = nums[i];do{int ne = (j + k) % n;swap(nums[ne], pre);j = ne;} while(i != j);}}