算法题002 程序员编程艺术第一章 左旋转字符串

题目描述

　　题目来源&＃xff1a;http://blog.csdn.net/v_JULY_v/article/details/6322882

　　定义字符串的左旋转操作&＃xff1a;把字符串前面的若干个&＃xff08;K个&＃xff09;字符移动到字符串的尾部。

　　如把字符串abcdef左旋转2位得到字符串cdefab。

　　请实现字符串左旋转的函数&＃xff0c;要求对长度为n的字符串操作的时间复杂度为O(n)&＃xff0c;空间复杂度为O(1)。

题目分析

　　如果采用每次将数组中的元素移动一位&＃xff0c;循环K次的方法&＃xff0c;则时间复杂度为O(K * n)&＃xff0c;只需要额外的一个存储空间。但是这是不合时间复杂度要求的。

　　另外需要注意的是K不一定会小于n&＃xff0c;所以需要取K &＃61; K % n。

　　但是这还是不能实现线性复杂度&＃xff0c;编程之美上通过右移字符串提出了一个三次翻转的算法。

三次翻转的算法

　　可以看到不管是左移还是右移&＃xff0c;其结果都是两段子串交换了位置。

　　如123abcd这个串&＃xff0c;左移三位得到abcd123&＃xff0c;实际上是123和abcd交换了位置。

　　怎么在线性复杂度内实现这种位置交换呢&＃xff1f;三次翻转是这样做到的&＃xff1a;

　　首先&＃xff0c;将123翻转成逆序&＃xff1a;321abcd

　　然后&＃xff0c;将abcd翻转成逆序&＃xff1a;321dcba

　　最后&＃xff0c;将整个串再翻转一遍&＃xff1a;abcd123&＃xff08;得到左移结果&＃xff09;。

　　通常情况的描述&＃xff1a;

　　1.根据要移动的位数把字符串划分成两段&＃xff1a;XY&＃xff1b;

　　2.翻转X子段&＃xff1b;

　　3.翻转Y子段&＃xff1b;

　　4.将得到的结果整个翻转。

实现代码

LeftRotate实现

#include
#include <string>
using namespace std;void ReverseString(string &str)
{int startID &＃61; 0;int endID &＃61; str.size() - 1;char temp &＃61; &＃39; &＃39;;while(startID < endID){temp &＃61; str[startID];str[startID] &＃61; str[endID];str[endID] &＃61; temp;&＃43;&＃43;startID;--endID; }//cout<
}int main(int argc, char* argv[])
{string str;int k;while(cin >> str >> k){//首先将k取余数&＃xff0c;避免k比串长还大的情况k &＃61; k % str.size();//cout <<"k: "<//得到子串string x &＃61; str.substr(0,k);//cout <<"x: " <string y &＃61; str.substr(k,str.size());//cout <<"y" <//需要注意substr()方法含左不含右//三次翻转算法
ReverseString(x);ReverseString(y);string result &＃61; x &＃43; y;ReverseString(result);cout <<"The final result is: " < endl;}return 0;
}

测试用例

　　因为没找到Online Judge&＃xff0c;所以自己设计的测试用例&＃xff1a;

　　输入&＃xff1a;

1234567ABDCD 3

123 6

abcd 25

1234567 0

g 10

　　输出&＃xff1a;

The final result is: 4567ABDCD123

The final result is: 123

The final result is: bcda

The final result is: 1234567

The final result is: g

参考资料

　　程序员编程艺术第一~二十七章集锦与总结

http://blog.csdn.net/v_july_v/article/details/7506231

　　程序员编程艺术第一章 左旋转字符串

http://blog.csdn.net/v_JULY_v/article/details/6322882

　　搜索到的实现&＃xff1a;

http://www.cnblogs.com/aLittleBitCool/archive/2011/02/22/1961267.html

http://www.cnblogs.com/mingzi/archive/2009/08/04/1538482.html