【字符串】旋转字符串(左旋或右旋k个字符)

问题描述

将N个字符的数组，循环右移K位。时间复杂度O(N)。 比如原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。

问题分析

方法1、暴力位移法，时间复杂度为O(m*n)

下面是左旋的方法，

void LeftShift1(char *str,size_t len, size_t n) { //n >len的情况 if (n == len || n == 0 || len == 0) return; n %= len; while (n--) { //先移一位 char tmp = str[0]; for (size_t i = 0; i < len - 1; ++i) { str[i] = str[i + 1]; } str[len - 1] = tmp; } }

方法2、指针翻转法，时间复杂度为O(m+n)

就是以n个字符为单位，进行移动，当剩余元素不够k个元素时，1个1个进行移动。

void LeftShift2(string &str, size_t n) { //例子abc def ghi jk 左移三位 size_t len = str.length(); if (len == n || n == 0 || len == 0) return; n %= len; int p1 = 0, p2 = n; //计算循环多少次 int k = len - n - len%n; // // while (k--) { std::swap(str[p1], str[p2]); ++p1; ++p2; } //末尾留有位置 int r = len - p2; while (r--) { int i = p2; //从p2位置开始前移(1位1位的移动) while (i > p1) { std::swap(str[i], str[i - 1]); i--; } p1++; p2++; } }

方法3、时间复杂度为O(n)

(1)思路1、 就是将原数组，分为两个部分，分别将这两个部分逆序，然后再将逆序后字符串，再进行逆序 步骤：

1.逆序排列 abcd: abcd1234 -> dcba1234; 2.逆序排列 1234: dcba1234-> dcba4321; 3.全部逆序 dcba4321->1234abcd。

//方法4、就是将字符串分为两个部分，分别逆序，然后再将整体逆序 void ReverseStr(char *str, int begin, int end) { for (; begin < end; begin++, end--) std::swap(str[begin], str[end]); } void RightShift4(char *str,int len,int n) { n = n % len; ReverseStr(str, 0, n-1); ReverseStr(str, n, len -1); ReverseStr(str, 0, len - 1); cout << str << endl; }

(2)思路2: 方法简单到爆，重新开辟同样的空间大小，将原数组中的内容，按旋转之后的顺序放置。

void RightShift3(string &str,size_t n) { size_t len = str.size(); string temp(len,0); n = n %len; for (size_t i = 0; i < len; ++i) { temp[(i + n) % len] = str[i]; } str = temp; }