字符串逆轉(zhuǎn)問題
問題描述：
長度為n的字符串，在第 i 的位置處向左旋轉(zhuǎn)或者向右旋轉(zhuǎn)。比如字符串a(chǎn)bcdefgh 長度n為8 ，若將該字符串在i=3的
位置處，向左旋轉(zhuǎn)則得到字符串defghabc 。
問題要求：
時(shí)間復(fù)雜度要和n成正比，內(nèi)存幾十字節(jié)。
問題解決方法：
數(shù)學(xué)基礎(chǔ) 即將矩陣 AB 變?yōu)锽A 。
AB---> A'B--->A'B'------>(A'B')'--------->BA 。 其中 ' 表示矩陣的轉(zhuǎn)置。
解決方法：
將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)
總結(jié)：
通過上述(1)，(2)，(3) 即完成了字符串轉(zhuǎn)置 。每一個(gè)reverse() 函數(shù)的時(shí)間復(fù)雜度均為o(n) ，空間復(fù)雜度只利用了一個(gè)
臨時(shí)變量，滿足上述要求。
#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 ;
}