一 问题描述
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。
二 解题思路
定义一种字符串转置操作XT--将字符串反转可以验证(XT)T=X (XY)T=YTXT 原有字符串为XY,左移后的字符串应该是YX 那么有(XTYT)T=(YT)T(XT)T=YX
三 代码
/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:字符串转置的应用--
*定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字
*符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度
*为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。
*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*E-mail: 2363702560@qq.com
*Date: 2012/12/6
*/
/*
定义一种字符串转置操作XT--将字符串反转
可以验证(XT)T=X (XY)T=YTXT
原有字符串为XY,左移后的字符串应该是YX
那么有(XTYT)T=(YT)T(XT)T=YX
*/
#include <iostream>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
private:
string str;
void Reverse(string::iterator beg,string::iterator end) {
while(beg!=end) {
swap(*beg++,*--end);
}
}
public:
Solution(const string &input) {
str=input;
}
void JustDoIt(int n) {
if(n<0) {
cerr<<"参数有误!"<<endl;
exit(1);
}
if(n>str.size()) n-str.size();
Reverse(str.begin(),str.begin()+n); //XT
Reverse(str.begin()+n,str.end()); //YT
Reverse(str.begin(),str.end()); //(XTYT)T
}
void show() {
cout<<"左旋后的字符串是:"<<str<<endl;
}
};
void main() {
Solution s("Hello world, I am wangzhicheng");
s.JustDoIt(2);
s.show();
}
四 测试：
