【程序猿编程艺术】学习记录1：左旋转字符串之指针翻转法
题目：左旋转字符串
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部，如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)。空间复杂度为O(n)
思路一、暴力移位法
//暴力移位法
void leftshiftone(char *s, int n)
{
char t = s[0];
for(int i = 1;i < n; i++)
s[i-1] = s[i];
s[n-1] = t;
}
void leftshift(char *s, int n, int m)
{
while(m--)
leftshiftone(s,n);
}
思路二、指针翻转法
參考代码：
#include <iostream>
#include <string>
using namespace std;
void rotate(string &str, int m)
{
if(str.length() == 0 || m <= 0)
return;
int n = str.length();
//处理m>n的情况
if(m % n <= 0)
return;
int p1 = 0,p2 = m;
int k = (n - m) - n % m;
//交换p1、p2指向的元素，之后移动p1，p2
while(k --)
{
swap(str[p1], str[p2]);
p1++;
p2++;
}
//处理尾部，r为尾部左移次数
int r = n - p2;
while(r--)
{
int i = p2;
while(i > p1)
{
swap(str[i], str[i-1]);
i--;
}
p2++;
p1++;
}
}
int main()
{
string ch = "abcdefghijk";
rotate(ch, 3);
cout << ch << endl;
return 0;
}
swap交换函数
思路三、
參考代码：
#include <iostream>
#include <string>
using namespace std;
void rotate(string &str, int m)
{
if(str.length() == 0 || m < 0)
return;
//初始化p1p2
int p1 = 0,p2 = m;
int n = str.length();
//处理m大于n
if(m%n == 0)
return;
//循环至p2到达字符串的末尾
while(true)
{
swap(str[p1],str[p2]);
p1++;
if(p2 < n+1)
p2++;
else
break;
}
//处理尾部。r为尾部循环左移动的次数
int r = m - n%m;
while(r--)
{
int i = p1;
char temp = str[p1];
while(i < p2)
{
str[i] = str[i+1];
i++;
}
str[p2] = temp;
}
}
思路4、上述都是如果m<n，我们如今考虑m为负数和m大于n的可能
參考代码：
#include <iostream>
#include <string>
using namespace std;
//const int positiveMod(m,n) = (m % n + n) % n; //无效
//#define positiveMod(m,n) ((m) % (n) + (n)) % (n) //宏定义切记这里不能加上；号
inline int positiveMod(int m, int n) //内联
{
return ((m) % (n) + (n)) % (n);
}
//左旋转字符串str,假设m为负数。则有右旋转
void rotate(string &str, int m)
{
if(str.length() == 0)
return;
//初始化
int n = str.length();
int p1 = 0,p2 = m;
//处理m大于n以及m为负数的情况，positiveMod
m = positiveMod(m,n);
if(m == 0)
return;
int round;
//p2当前所指和之后的m-1个字母共m个字母，就能够和p2前面的m个字母交换
while(p2 + m - 1 < n)
{
round = m;
while(round--)
{
swap(str[p1], str[p2]);
p1++;
p2++;
}
}
//剩下的不足m个字母一个一个交换
int r = n - p2;
while(r--)
{
int i = p2;
while(i > p1)
{
swap(str[i], str[i-1]);
i--;
}
p2++;
p1++;
}
}
//測试
int main()
{
cout << ((-15)%7 + 7)%7 << endl;
cout << (-15)%7 << endl;
string ch = "abcdefg";
int len = ch.length();
for(int m = -2*len; m <= len * 2; m++)
{
//因为传给rotate的是string的引用。所以每次调用都用一个新字符
string s = "abcdefg";
rotate(s,m);
cout << positiveMod(m,len) << ": " << s << endl;
}
return 0;
}
思路5、递归转换法
參考代码：
#include <iostream>
using namespace std;
void rotate(string &str, int n, int m, int head, int tail, bool flag)
{
//n表示待处理的字符串长度。m为待处理部分的旋转长度
//head:待处理部分的头指针 tail待处理部分的尾指针
//flag = true表示左旋，否则右旋
//返回条件
if(head == tail || m <= 0)
return;
if(flag == true)
{
int p1 = head;
int p2 = head + m;
int k = (n-m) - n % m; //p1,p2移动距离，向右
for(int i = 0; i < k; i++,p1++,p2++)
swap(str[p1], str[p2]);
//结束左旋进入右旋
rotate(str, n-k, n %m, p1, tail, false);
}
else
{
int p1 = tail;
int p2 = tail - m;
//p1,p2移动距离
int k = (n-m)-n%m;
for(int i = 0; i < k; i++, p1--,p2--)
swap(str[p1],str[p2]);
rotate(str,n-k,n % m, head, p1, true);
}
}
int main()
{
int i = 3;
string str = "abcdefghijk";
int len = str.length();
rotate(str,len, i%len ,0,len-1,true);
cout << str.c_str() << endl;//转化成字符数组的形式输出
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。