43.左旋转字符串.md

43.左旋转字符串

题目描述

• 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

 

解题思路

• 我的思路一，备份移位法。复制前面的部分到临时字符串，把后面的部分向前移动，然后再把刚才复制出来的放到后面。

• 我的思路二，空串填充法。创建一个新的字符串，然后把后面的部分先填进去，再把前面的部分填到后面。

• 《剑指offer》。由《44.翻转单词顺序》得到启发，该题目中创建了一个函数，可以将给定字符串翻转（通过两个指针向中间逼近互换实现）。本题可以先根据左旋的位数将字符串分为两部分，比如abcdefg左旋2位就可以把ab分为一组，剩下的分为另一组，首先使用上面的函数将两组分别翻转，然后再使用上面的函数将整个字符串翻转即可。

• 左移次数可以先和字符串长度取余数，因为如果次数大于字符串长度的话就重复了。

• 上面几种方法在牛客上耗时和占用空间差不多，都是3ms，484K，感觉不是很精确。

 

代码

• 我的思路一，备份移位法

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int length = str.length();
        if(length<2) return str;
        n = n % length;
        string tmpStr = string(str, 0, n);  // 从第0位开始拷贝n位
        for(int i=n; i<length; i++) str[i-n] = str[i];
        for(int i=0; i<n; i++) str[length-n+i] = tmpStr[i];
        return str;
    }
};

• 我的思路二，空串填充法

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int length = str.length();
        if(length<2) return str;
        n = n % length;
        string tmpStr;
        tmpStr.append(str, n, length-n);
        tmpStr.append(str, 0, n);
        return tmpStr;
    }
};

• 剑指offer，翻转字符串法，实现一，手动翻转

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int length = str.length();
        if(length<2) return str;
        n = n % length;
        for(int i=0, j=n-1; i<j; i++, j--) swap(str[i], str[j]);
        for(int i=n, j=length-1; i<j; i++, j--) swap(str[i], str[j]);
        for(int i=0, j=length-1; i<j; i++, j--) swap(str[i], str[j]);
        return str;
    }
};

• 剑指offer，翻转字符串法，实现二，标准库std::reverse()函数翻转

  //first迭代器指向第一个元素，last迭代器指向最后一个元素的下一个位置，即左闭右开
  //如果字符串str整个翻转的话就是reverse(str.begin(), str.end())
  void reverse( BidirIt first, BidirIt last ); 

  代码：

class Solution {
0public:
    string LeftRotateString(string str, int n) {
        int length = str.length();
        if(length<2) return str;
        n = n % length;
        reverse(str.begin(), str.begin()+n);
        reverse(str.begin()+n, str.end());
        reverse(str.begin(), str.end());
        return str;
    }
};