剑指Offer JZ43 左旋转字符串 C++实现

题目描述

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

解题思路

方法一：遍历

1、思路：当K小于字符串长度时，循环左移K位就是把字符串前K位放到字符串末尾。

2、代码：

class Solution {
public:string LeftRotateString(string str, int n) {string result = "";if (str.empty()) return result;int len = str.length();if (n > len) n %= len;for (int i = n; i < len; i++) {result += str[i];}for (int i = 0; i < n; i++) {result += str[i];}return result;}
};

3、复杂度：

时间复杂度：O(n)；

空间复杂度：O(n)。

方法二：字符串反转

1、思路：当K小于字符串长度时，可以先反转前K位字符，再反转第K+1到第n位字符，最后将字符串整体反转，就可以得到循环左移K位的效果，这样做还是比较巧妙的。

2、代码：

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

3、复杂度：

时间复杂度：O(n)；

空间复杂度：O(1)。