【剑指Offer-知识迁移能力】面试题58.2：左旋转字符串

题目描述

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

思路1

左旋转实际上就是把字符串分为两部分，然后颠倒一下两部分的顺序。如果字符串时string类型的话，可以直接用substr来做。代码如下：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(str=="")
            return "";
        
        string part1 = str.substr(0, n);
        string part2 = str.substr(n, str.length()-n);
        return part2+part1;
    }
};

思路2

思路1并不是这题的本意（虽然个人觉得思路1方法代码都更简单）。这题是面试题58：翻转单词顺序的延伸，所以可以用类似的方法来做。假设我们要翻转句子中单词的顺序，例如“hello world”，翻转为“world hello”，这相当于把hello移到了world后面（并不完全一样，因为有空格，但思想是类似的）。对于这个问题，我们可以把字符串分为两部分，例如把“abcXYZdef”前3位“abc”放到后面，也就是分为“abc”“XYZdef”两部分，我们先分别翻转这两部分，得到“cba”“fedZYX”，然后翻转整个字符串，得到“XYZdefabc”。所以过程是：
(1)将字符串根据位置分为两部分；
(2)分别翻转这两部分；
(3)将两部分作为一个整体翻转。
代码如下：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(str=="")
            return "";
        
        string part1 = str.substr(0, n);
        string part2 = str.substr(n, str.length()-n);
        part1 = reverse(part1);
        part2 = reverse(part2);
        str = part1+part2;
        return reverse(str);
    }
    
    string reverse(string str){
        int left = 0;
        int right = str.length()-1;
        while(left<right){
            swap(str[left], str[right]);
            left++;
            right--;
        }
        return str;
    }
};

如果字符串是string类型的，这种方法确实是把简单问题复杂化了。这种方法适合使用字符数组表示字符串的情况。