左旋转字符串

五种题解，借鉴了官方题解和leetcode旋转数组题解。

/*
*方法一：新建字符串复制
*/
class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(n>str.length())
            return str;
        string s="";
        for(int i=n;i<str.length();i++){
            s+=str[i];
        }
        for(int i=0;i<n;i++){
            s+=str[i];
        }
        return s;
    }
};

/*
*方法二：使用STL
*/
class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(n>str.length())
            return str;
        return str.substr(n)+str.substr(0,n);
    }
};

这两种都需要n的空间复杂度。
以下三种空间复杂度都为O(1)，但是修改了原字符串，其实更适用于数组的左移。

/*
*方法三：暴力法（空间复杂度为O(n*k)）
*/
class Solution {
public:
    string LeftRotateString(string str, int n) {
        char previous;
        for (int i = 0; i < n; i++) {
            previous = str[0];
            for (int j = str.length()-1; j >= 0; j--) {//每个值都改变一下
                swap(previous,str[j]);
            }
        }
        return str;
    }
};

/*
*方法四：反转法
*/
class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(str.size()<2){
            return string();
        }
        int len=str.length();
        n %= len;
        reverse(str,0,len-1);
        reverse(str,0,len-n-1);
        reverse(str,len-n,len-1);
        return str;
    }
    void reverse(string& str,int l,int r){
        while(l<r){
            char tmp=str[l];
            str[l]=str[r];
            str[r]=tmp;
            l++;
            r--;
        }
    }
};

/*
*方法五：环状替代
*/

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(str.size()<2)
            return string();
        n%=str.size();
        int cnt=0;
        for(int start=0;cnt<str.size();start++){
            int cur=start;
            int pre=str[start];
            do{
                int next=(cur-n+str.size())%str.size();
                int tmp=str[next];
                str[next]=pre;
                pre=tmp;
                cur=next;
                cnt++;
            }while(cur!=start);
        }
        return str;
    }
};