题解 | #左旋转字符串#

题解一：字符切分与拼接
解题思路： 获取str[n:] 和 str[:n]子串，目标串target = str[:n] + str[n:];
如样例：

复杂度分析：
时间复杂度： O(N)，需要遍历把子串拷贝出新的内存空间
空间复杂度： O(N)，需要申请空间存储两段str子串的长度

class Solution {
public:
    string LeftRotateString(string str,int n){
        if(str.size()==0) return str;
        string s = str.substr(0,n);
        string res = str.substr(n,str.size()-n) + s;
        return res;
    }
};

题解二：不使用substr函数，字符串遍历
解题思路：利用取余操作得到目标串target应该是str中哪个字符。
主要思路：
1. 首先，n如果是str长度的倍数，那么最终目标串target是和str一样的，令left = n%len。
2. 如果left = 0 ,那么直接返回原串，否则进行字符串遍历。
3. target每个位置的字符为str[ (left+i)%str.size()] ,i代表当前位置。
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N)

class Solution {
public:
   string moveleft (string s,int r){
        string target = "";
        for(int i = 0;i<s.size();i++){
            target+=s[(i+r)%s.size()];
        }
        return target;
    } 

    string LeftRotateString(string str, int n) {
       int len = str.size();
       if(len==0) return str;
       int left = n%len;//处理长度超过str本身长度的情况；
       if(left==0) return str;
       else return moveleft(str,left);
    }
};

题解三：局部翻转+整体翻转
解题思路：首先翻转str[:n]子串，其次翻转str[n:]子串，最后翻转str.
如样例：

复杂度分析：
时间复杂度： O(N)
空间复杂度： O(1)

class Solution {
public:
    string LeftRotateString(string str, int n) {
       int len = str.size();
       if(len==0) return str;
       int left = n%len;//处理长度超过str本身长度的情况；
       if(left==0) return str;//特判，避免剩下的多余两次反转；
       reverse(str.begin(),str.begin()+left);
       reverse(str.begin()+left,str.end());
       reverse(str.begin(),str.end());
       return str;
    }
};