字符串逆轉問題
問題描述：
長度為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 ;
}