剑指offer：左旋转字符串

题目描述：

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

思路分析：

1. 第一个想到的方法就是利用一个辅助空间来完成，对于输入k的长度实际上当它大于字符串的长度时，真正进行左旋转操作的就只有n%str.length()次，因此通过%操作来确认在哪个位置将原字符串分开。之后用两个for循环分别给新字符串赋值即可。

2. 不利用辅助空间的方式。可以发现对于字符串实际可以划分为两部分，第一部分为进行了左移操作的字符串，第二部分为未进行左移操作的字符串。那么由于是循环左移，实际就是需要将第一部分字符串的头与第二部分字符串的尾相连，那么可以考虑用翻转的方式，首先翻转第一部分字符串为“ZYXdefabc”，再翻转第二部分字符串为"ZYXcbafed"，此时就将两部分的头尾相连，最后再将整体的字符串进行一次翻转，就为所求的结果"defabcXYZ"。时间复杂度为O(n)，空间复杂度为O(1)。

代码：

思路一：

 1 class Solution {
 2 public:
 3     string LeftRotateString(string str, int n) {
 4         int len = str.length();
 5         if(len<=0 || n<=0)
 6             return str;
 7         n = n%len;
 8         string new_str = str;
 9         int index = 0;
10         for(int i=n; i<len; i++)
11         {
12             new_str[index] = str[i];
13             index++;
14         }
15         for(int i=0;i<n; i++)
16         {
17             new_str[index] = str[i];
18             index++;
19         }
20         return new_str;
21     }
22 };

思路二：

 1 class Solution {
 2 public:
 3     string LeftRotateString(string str, int n) {
 4         int len = str.length();
 5         if(len<=0 || n<=0)
 6             return str;
 7         Inverse(str, 0, n-1);
 8         Inverse(str, n, len-1);
 9         Inverse(str, 0, len-1);
10         return str;
11     }
12     void Inverse(string &str, int l, int r)
13     {
14         for(int i=l; i<=(l+r)/2; i++)
15         {
16             swap(str[i], str[l+r-i]);
17         }
18     }
19 };