Created
September 5, 2013 23:28
-
-
Save lubobill1990/6457632 to your computer and use it in GitHub Desktop.
shift a string to right and left in O(n) time and O(1) memory
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstring> | |
#include <cstdlib> | |
#include <iostream> | |
using namespace std; | |
inline int rightshiftindex(int index,int offset, int len){ | |
if(index+offset>=len){ | |
return (index+offset)-len; | |
} | |
} | |
void _strrightshift(char *str, int offset, int len){ | |
char tmp_latter,tmp; | |
char count; | |
int index,index_next_round; | |
int curr_start=0; | |
index=curr_start; | |
tmp_latter=str[curr_start]; | |
while(true){ | |
if(count>=len){ | |
break; | |
} | |
index_next_round=rightshiftindex(index,offset,len); | |
tmp=str[index_next_round]; | |
str[index_next_round]=tmp_latter; | |
tmp_latter=tmp; | |
++count; | |
index=rightshiftindex(index,offset,len); | |
if(index==curr_start){ | |
curr_start=++index; | |
tmp_latter=str[curr_start]; | |
} | |
} | |
} | |
void _strleftshift(char *str, int offset, int len){ | |
int count=0; //已经转换了多少字符 | |
int curr_start=0; //本轮开始的index | |
int index=curr_start; | |
int next_index; | |
char first_tmp; | |
while(true){ | |
if(count>=len){ | |
break; | |
} | |
if(index==curr_start){ | |
first_tmp=str[index]; | |
} | |
next_index=rightshiftindex(index,offset,len); | |
if(next_index==curr_start){ | |
str[index]=first_tmp; | |
}else{ | |
str[index]=str[next_index]; | |
} | |
index=next_index; | |
++count; | |
if(index==curr_start){ | |
curr_start=++index; | |
} | |
} | |
} | |
void strrightshift(char *str, int offset, int len=0){ | |
if(len==0){ | |
len=strlen(str); | |
} | |
offset=offset%len; | |
if(offset>len/2){ | |
_strleftshift(str,len-offset,len); | |
}else{ | |
_strrightshift(str,offset,len); | |
} | |
} | |
void strleftshift(char *str, int offset, int len=0){ | |
if(len==0){ | |
len=strlen(str); | |
} | |
offset=offset%len; | |
if(offset>len/2){ | |
_strrightshift(str,len-offset,len); | |
}else{ | |
_strleftshift(str,offset,len); | |
} | |
} | |
int main(int argc, const char *argv[]) | |
{ | |
char a[100]; | |
char b[16]; | |
strcpy(a,argv[1]); | |
strcpy(b,argv[2]); | |
strrightshift(a,atoi(b)); | |
cout<<a<<endl; | |
strleftshift(a,atoi(b)); | |
cout<<a<<endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment