左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

解题思路:

方法一：直接法，定义一个左移一位函数leftmove，先定义一个char temp = s[0];。其余s[i]==s[i+1];，n-1位置最后一个字符替换为temp。左移几位就循环几次左移函数。

方法二：利用reverse函数，原理：YX=(X^T Y^T)^T

以”abcdefg“为例，我们可以把它分为两部分。由于想把它的前两个字.符移到后面，我们就把前两个字符分到第一部分，把后面的所有字符分到第二部分。我们先分别翻转这两部分，于是就得到”bagfedc“。接下来翻转整个字符串，得到的”cdefgab“刚好就是把原始字符串左旋转两位的结果。

方法三：取巧法，s+=s;，复制一遍字符串，从n开始处截取原字符串长度返回即可。

时间复杂度

O(kn) n为字符串长度，k旋转位数
O(n)
O(n)

空间复杂度

O(1)
O(1)
O(n)

代码

方法一：直接左移(超时)

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        for (int i=0;i<n;i++)
        {
            leftMove(s);
        }
        return s;
    }
    void leftMove(string &s)
    {
        int m  = s.size();
        char temp = s[0];
        for (int i=0;i<m;i++)
        {
            if (i!=m-1)
            {
                s[i]=s[i+1];
            }
            else
            {
                s[i] = temp;
            }
        }
    }
};

方法二：YX=(X^T Y^T)^^T

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.begin()+n); 
        //reverse函数反转的范围是[first,last)
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }
};

方法三：s+=s

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int m = s.size();
        s+=s;
        s = s.substr(n,m);
        return s;
    }
};

空间复杂度改善为O(1)

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int m = s.size();
        string res = "";
        for(int i=n;i<n+m;i++)
        {
            res+=s[i%m];
        }
        return res;
    }
};