21左轉(zhuǎn)字符串
一 問題描述
對(duì)字符串進(jìn)行左旋轉(zhuǎn)操作，比如字符串為 cdefab ,執(zhí)行左旋轉(zhuǎn)2操作之后，字符串變?yōu)閑fabcd 。要求使用o(n)的時(shí)間復(fù)雜度 和o(1)的空間完成。
考慮之前實(shí)現(xiàn)的字符串中單詞翻轉(zhuǎn)問題 I am a student. 問題設(shè)單詞劃分為AB 兩部分 ，則BA = (AT BT)T。
即先對(duì)A部分逆轉(zhuǎn)，再對(duì)B部分逆轉(zhuǎn)，最后再對(duì)上述中間結(jié)果，進(jìn)行逆轉(zhuǎn) 。
二 代碼描述
#include <iostream>
using namespace std ;
void reverse(char * l , char * h) //實(shí)現(xiàn)逆轉(zhuǎn)
{
if(l == 0 || h == 0)
return ;
while(l < h)
{
swap(*l ,*h) ;
l++ ;
h-- ;
}
}
void leftreverse(char * s, int k , int n)
{
if(k > n )
return ;
char * t = s + k - 1;
char * end = s + n -1 ;
reverse(s , t) ;
reverse(t + 1 , end) ;
reverse(s , end) ;
}
int main()
{
char s[100] = "dsadsda" ; //char *s 為字符串常量
leftreverse(s , 3 , strlen(s)) ;
cout<<s<<endl;
system("pause") ;
return 0 ;
}