leetcode刷题笔记189

写在前边

很简单的一道题目，我怀疑我们期末考试就会考这样的题目，刚巧拿这个练练手。

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [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:

输入: [-1,-100,3,99] 和 k = 2

输出: [3,99,-1,-100]

解释:

向右旋转 1 步: [99,-1,-100,3]

向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

要求使用空间复杂度为 O(1) 的 原地 算法。

难就难在需要O（1）的空间复杂度，刚开始做会觉得有点棘手，但是知道怎么做之后，会觉得特别巧妙，本质还是用数学的思想。

设有一个字符串ABCDEFG

易知，将该字符串完全倒序，会得到GFEDCBA，而如果将前四个倒序，是DCBAEFG，可以看到，这里实现了局部的倒序，如果再将整个字符串倒序呢？会得到GFEABCD，会发现，ABCD的顺序没有发生变化，只是往后移动了几位，而如果将前后分别倒序，再整个倒序的话，可以很轻松的得到我们要的结果，如：将前四位，后四位分别倒序，得到DCBAGFE，再将整个倒序，得到EFGABCD，与将ABCDEFG按照题目的方式进行移动得到的结果一模一样！

按照这样的的思想，我们很容易就能解出来这道题。交答案的时候WA了一次，是因为没有考虑到移动位数大于整个数组的长度，这个时候需要取模。

源码如下：

#include"iostream"
#include"algorithm"
#include"vector"
using namespace std;
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int>::iterator it;
        it=nums.begin();
        if(nums.size()>1)
        {
            if(nums.size()-k<0);
            {
                k=k%nums.size();
            }
            it=it+nums.size()-k;
            reverse(nums.begin(),it);

            reverse(it,nums.end());

            reverse(nums.begin(),nums.end());
        }
    }
};
int main()
{
    vector<int> temp={-1,-100,3,99};
    Solution s;
    s.rotate(temp,100);
    for(int i=0;i<temp.size();i++)
    {
        cout<<temp[i]<<endl;
    }
    system("pause");
    return 0;
}
           

记得学会使用stl,像这里直接用reverse（），很方便。