剑指offer 58 2 左旋转字符串

将左边n个字符转移到字符串结尾，比如 s=abcdefg ，n=2；输出cdefgab。看起来不难，但是解法还是挺多的，重要的是复杂度。

还是先写下思路，

常规的思路（暴力）：就是定义两个字符串str1，str2，n之后的字符全部拷贝进入str2，然后再把k和k之前字符的拷贝进入str1，返回str2+str1。 缺点嘛，空间复杂度高，时间复杂度也就O(N)，代码如下。

class Solution {
public:
    string reverseLeftWords(string s, int n) {
    string str1,str2;

for(int i=0;i<n;i++)
{
    str1+=s[i];
}

for(int i=n;i<s.size();i++)
{
    str2+=s[i];
}

return str2+str1;
    }
};

那就稍微降低一下空间复杂度：就定义一个字符串，把n和n之前的字符拷贝进去，原本的字符串从n位置开始向前移动n个位置，然后重置s的大小，返回s+str，感觉并没有降低多少空间复杂度.....代码如下

class Solution {
public:
    string reverseLeftWords(string s, int n) {
string str;
for(int i=0;i<n;i++)
{
    str+=s[i];
}

for(int i=0;i<s.size()-n;i++)
{
    s[i]=s[i+n];
}
s.resize(s.size()-n);

return s+str;
    }
};

思考一下空间复杂度更小的解法：反正c++都支持原地修改了字符串了，我直接原地替换算了，0号位的字符和0+n的替换，1和1+n的替换，....n-1和 n-1+n的替换，这么说有点抽象，就是把前n个字符统统向后移动了一个位置，然后再移动一个位置，接下来再移动一个位置，直到我们的n-1这个位置的数移动到了字符串的末端 。，问题是这样的空间复杂度确实低了，只有O(1)，但是时间复杂度蹭蹭的往上涨，也不太好。代码如下

class Solution {
public:
    string reverseLeftWords(string s, int n) {
int count=n;
while(count<s.size())
{
for(int i=count-1;i>=count-n;i--)
{
    char temp=s[i+1];
    s[i+1]=s[i];
    s[i]=temp;
}
count++;
}

return s;
    }
};

还有什么解法呢？swap()函数，我想到了这个，但是需要解决一些问题，首先字符串的长度必须是n的整数倍，如果不是，需要对原字符串扩容在减容，扩容后的位置用‘#’代替，交换完后，删除里面的‘#’，然后减容到原来的长度。具体代码如下

class Solution {
public:
    string reverseLeftWords(string s, int n) {
int length1=s.size();
int length2=length1-length1%n+n;
if(length1%n!=0){  s.resize(length2,'#');}

int key=0;
while(key<s.size()-n)
{
    for(int i=key;i<key+n;i++)
    {
        swap(s[i],s[i+n]);
    }
key+=n;
}

remove(s.begin(),s.end(),'#');
s.resize(length1);
return s;
    }
};

嗯 还有别的，有空再写。