剑指 Offer 58 - II. 左旋转字符串

剑指 Offer 58 - II. 左旋转字符串

</br></br>

题目：

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

示例1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

1 <= k < s.length <= 10000

</br></br>

思路一：

可以实例化一个新的string类的字符串，先将原字符串中下标为k的元素开始将其赋值到新的字符串中，再将原子符串中从0开始到k-1的元素赋值到新字符串中，因为只是将字符调换顺序，所以新字符串的大小和原子符串大小相同。如示例1中abcdefg字符串k = 2，那么就从下标为2的元素开始赋值给新的字符串，将k ~ s.size()-1的元素遍历赋值完之后，此时新字符串为cdefg；再从原子符串的头部开始遍历到k-1，再依次赋值给新字符串，此时新字符串就是cdefgab。

注意：当k > s.size()时，通过k = n % s.size()找到有意义旋转次数，避免无意义旋转，减少时间成本。

代码如下：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int k = n % s.size(); //找到有意义旋转次数，避免无意义旋转。
        string s1; //新定义字符串
        int size = s.size(); //字符串大小
        s1.resize(size);//开空间
        int i = k;
        int j = 0;
        //将k~size-1的元素赋值给新字符串
        while(i < size ) 
        {
            s1[j++] = s[i++];
        }
        //将0~k-1的元素赋值给新字符串
        i = 0;
        while(j < size)
        {
            s1[j++] = s[i++];
        }
        return s1;
    }
};

时间复杂度：O(N)

空间复杂度：O(N)

</br></br>

思路二：

通过反转函数实现旋转。

1.先将k ~ size - 1的元素反转，如示例1中abcdefg字符串将 k ~ size - 1反转后为abgfedc；

2.再将0 ~ k - 1的元素反转，示例1中经过第一次反转之后再经过本次反转就变成bagfedc；

3.最后将整体反转，即0 ~ size - 1反转，经过本次反转就变成cdefgab。

代码如下：

代码1：自定义一个反转函数

class Solution {
public:
    //反转函数
    void Reverse(string& s, int left, int right)
    {
        while(left < right)
        {
            swap(s[left++],s[right--]);//使用swap函数实现交换
        }
    }
    string reverseLeftWords(string s, int n) {
        int size = s.size();
        int k = n % size;
        Reverse(s,k,size - 1); //将k ~ size - 1的元素反转
        Reverse(s,0,k - 1); //将0 ~ k - 1的元素反转
        Reverse(s,0, size - 1);//最后将整体反转
        return s;
    }
};

代码2：使用库中的反转函数

class Solution {
public:
    //反转函数
    string reverseLeftWords(string s, int n) {
        int size = s.size();
        int k = n % size;
        reverse(s.begin()+k,s.end()); //将k ~ size - 1的元素反转
        reverse(s.begin(),s.begin()+k); //将0 ~ k - 1的元素反转
        reverse(s.begin(),s.end());//最后将整体反转
        return s;
    }
};

时间复杂度：O(N)

空间复杂度：O(1)

</br></br>

思路三：

通过使用string类中的erase函数和push_back函数完成。如示例1中abcdefg字符串，k = 2，先将字符a保存起来，然后使用erase函数删除字符a，再将其尾插，形成字符串bcdefga；再将字符b保存起来，再删除尾插，形成字符串cdefgab。

此法仅供参考，并不推荐。

代码如下：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int k = n % s.size();
        while(k--)
        {
            char ch = s[0];
            s.erase(0,1);
            s.push_back(ch);
        }
        return s;
    }
};

时间复杂度：O(N)

空间复杂度：O(1)

【感谢龙石数据为本站数据中台建设方案 http://www.longshidata.com/pages/government.html，感恩 】