题目传送门：轮转数组
题目详情：
给你一个数组，将数组中的元素向右轮转
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 - 10 <= k <= 10^5
题目分析和代码：
起初并没有看到提示部分，自认为给的数组并不会很大，然后也没有深入思考，立刻就将代码写了出来。
初始超时代码（c++）：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int length=nums.size()-1;//数组下标最大值
while(k)//数组每向右移动一次执行一次循环直至移动k次
{
int t=nums[length];
for(int i=length;i>0;i--)//将数组第一个元素至倒数第二个元素中的每个元素都向右移动一位
{
nums[i]=nums[i-1];
}
nums[0]=t;
k--;
}
}
};时间复杂度为O(k*n)，空间复杂度为O(1)，虽然空间复杂度低但时间复杂度直接拉满了，题目数组范围太大因此在第35个测试用例超时了，当时我还很奇怪，点开查看最后的输入时才发现原来数组范围居然会这么大，开始认真思考解题方法了。
拿示例一来分析：输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
先将数组下标标出来：（）内为数组下标
输入: nums = [1（0）,2（1）,3（2）,4（3）,5（4）,6（5）,7（6）]
输出: [5（0）,6（1）,7（2）,1（3）,2（4）,3（5）,4（6）]
从上面我们可以看出数组下标为0的1移动到了数组下标为3的位置，数组下标为1的2则移动到了数组下标为4的位置，数组下标为6的7移动到了数组下标为2的位置，从其中我们可以发现元素下标的移动规律为：移动到(数组下标n+k)%数组长度的数组位置，(0+3)%7=3，(6+3)%7=2；找到规律后再将答案放到一个新开辟空间的数组中最后再转到原数组中，时间复杂度为O(n)，空间复杂度为O(n)。
第一次ac代码（c++）:
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int length=nums.size();
vector<int>ans(length,0);
for(int i=0;i<=length-1;i++)
{
int dis=(i+k)%length;
ans[dis]=nums[i];
}
for(int i=0;i<=length-1;i++)
{
nums[i]=ans[i];
}
}
};这样发现题目还是比较简单的，但是题目进阶要求时间复杂度为O(n),空间复杂度为O(1),空间复杂度为O(1)确实有点困难，看了官方题解三后发现居然还有这么神奇的方法，下面就简单讲解一下数组翻转的方法。
还是拿示例一来分析：输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
我们发现尾部k%数组长度的元素（5，6，7）移动到了数组头部，而其余元素则向后移动了k%数组长度的位置。
我们可以先将数组所有元素进行翻转，这样尾部的元素就会到达数组头部位置，然后再将头部前k%数组长度的元素翻转保证数组元素的顺序不变，然后再将其他元素进行翻转。
输入: nums = [1,2,3,4,5,6,7], k = 3
先将数组所有元素进行翻转: nums = [7,6,5,4,3,2,1]
然后再将头部3%7(7为数组长度)=前3个元素进行翻转: nums = [5,6,7,4,3,2,1]
再将其他元素进行翻转: nums = [5,6,7,1,2,3,4]
输出: [5,6,7,1,2,3,4]
数组翻转的代码（c++）：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums.begin(),nums.end());//翻转整个数组元素
reverse(nums.begin(),nums.begin()+k);//翻转前k个元素
reverse(nums.begin()+k,nums.end());//翻转其余元素
}
};reverse为c++函数，可以实现翻转数组，字符串，向量，使用时需要包含头文件<algorithm> 。
使用方法：翻转数组：reverse(a,a+n)n为数组元素个数；翻转vector中的元素或字符串时则为reverse(vec.begin() ,vec.end() ) 和 reverse(str.begin() ,str.end() )。
题目要求将数组进行向右旋转，如果是向左旋转的话只用将第一行翻转代码改到最后一行就行了，即为先翻转前n个元素，再翻转其余元素，最后翻转数组所有元素。
时间复杂度为O(n),空间复杂度为O(1)。
环状替换代码（c++）:
我们从初始位置 0 开始，最初令pre=nums[0]。可以得出位置 0 的元素会放到 (0+k)%n的位置，令 x= (0+k)%n，然后交换 pre 和 nums[x]，完成位置 x 的更新。然后，我们继续研究位置 x，并交换 pre 和 nums[(x+k)%n]，从而完成下一个位置的更新。如果回到初始起点0时还有元素未进行翻转，则将起点位置+1，然后重复上述内容直至一共翻转了n个元素（翻转完成）。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int length=nums.size(),count=length;
int i=0,pos=0,pre=nums[pos];//pre会不断更新成被覆盖的元素
if (k % length == 0)
return;
while (count--)//一共要对n个元素进行翻转，n为元素个数
{
pos = (pos + k) % length;
swap(nums[pos], pre);
if (pos == i)//如果回到起点且还有未遍历过的元素时
{
pos = ++i;
pre = nums[pos];
}
}
}
};时间复杂度为O(n),空间复杂度为O(1)。
计算机204 zjr