字符串逆转问题
问题描述：
长度为n的字符串，在第 i 的位置处向左旋转或者向右旋转。比如字符串abcdefgh 长度n为8 ，若将该字符串在i=3的
位置处，向左旋转则得到字符串defghabc 。
问题要求：
时间复杂度要和n成正比，内存几十字节。
问题解决方法：
数学基础 即将矩阵 AB 变为BA 。
AB---> A'B--->A'B'------>(A'B')'--------->BA 。 其中 ' 表示矩阵的转置。
解决方法：
将abc 看做A ，defgh 看做 B
具体算法：
（1） abcdefgh-----> cbadefgh reverse(0 ， i - 1)
（2） cbadefgh------> cbahgfed reverse( i , n - 1)
(3) cbahgfed ------> defghabc reverse(0 , n - 1)
总结：
通过上述(1)，(2)，(3) 即完成了字符串转置 。每一个reverse() 函数的时间复杂度均为o(n) ，空间复杂度只利用了一个
临时变量，满足上述要求。
#include <iostream>
#include <cstring>
using namespace std ;
const int SIZE = 40 ;
void reverse(char* a , int begin , int end)
{
int i = begin , j = end ;
int times = (j - i + 1) / 2 ;
int temp ;
while(times > 0)
{
temp = a[i] ;
a[i++] = a[j] ;
a[j--] = temp ;
times-- ;
}
}
int main()
{
int i ;
char str [SIZE] ;
cout<<"input str:";
cin>>str ;
cout<<"input i:" ;
cin>>i ;
reverse(str , 0 , i - 1) ;
reverse(str , i , strlen(str) - 1) ;
reverse(str , 0 , strlen(str) - 1) ;
for(int i = 0 ; i < strlen(str) ; i++)
cout<<str[i];
cin.get();
return 0 ;
}