lintcode8

给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)
样例
对于字符串 "abcdefg".
offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"
挑战
在数组上原地旋转，使用O(1)的额外空间

解1:
将数组右移一位，偏移量是offset，则循环offset%length次

void RightShift(string &arr,int offset)
{
    if(arr==NULL||offset==0)
        return;
    len=str.length();
    offset%=len;//偏移量可能大于数组长度，当偏移量等于数组长度时形同没有发生偏移
    while(offset--)
    {
        char tmp=arr[len-1];
        for(int i=len-1;i>0;i--)
        {
              arr[i]=arr[i-1];
        }
        arr[0]=tmp;
    }
}
//但是这个算法的时间复杂度为O(offset*length);

解2：
offset%=length;
如字符串"abcdefg",偏移量为3，则偏移后为"efgabcd"，则发现偏移后有两段的顺序是不变的（abcd和efg），即（0到length-offset-1）和（length-offset到length-1）这两段。要完成偏移也就是把这两段字符串整体调换位置即：abcd efg-->efg abcd
调换位置的实现可以通过逆序的完成：
1.前段字符串逆序abcd efg-->dcba efg
2.后段逆序dcba efg-->dcba gfe
3.整体逆序:dcba gfe-->efgabcd

void Reverse(string &arr,int begin,int end)
{
    for (; begin < end; begin++, end--)
    {
        char ch = arr[begin];
        arr[begin] = arr[end];
        arr[end] = ch;
    }
}
void rightshift(string &arr,int offset)
{
       if(arr==NULL||offset==0)
              return;
    int len = arr.length();
    offset %= len;
    Reverse(arr, 0, len - offset - 1);
    Reverse(arr, len - offset, len - 1);
    Reverse(arr, 0, len - 1);
}