下面描述兩種算法
空間復(fù)雜度都為O（1）
解法一
暴力移位
#define len(a) (sizeof(a)/sizeof(*a))
#include <stdio.h>
#include <assert.h>
void leftShiftOne(char* string, int length);
void leftRotateString(char* string, int length, int num);
int main(void){
char string[] = "asdfqwer";
printf("%s\n", string);
leftRotateString(string,len(string)-1,4);
printf("%s\n", string);
}
void leftShiftOne(char* string, int length) {
assert(string != NULL);
char tmp = string[0];
int i;
for(i=1; i < length; i++) {
string[i-1] = string[i];
}
string[length-1] = tmp;
}
void leftRotateString(char* string, int length, int num) {
assert(num>=0);
while(num--) {
leftShiftOne(string,length);
}
}
時(shí)間復(fù)雜度num*length
空間復(fù)雜度O(1)
解法二
三步反轉(zhuǎn)法
它基于一個(gè)公式
X="abc"
X^T="cba"
(X^T YT)T=YX
#include <stdio.h>
#include <assert.h>
#define len(a) (sizeof(a)/sizeof(*a))
void reverseString(char* s, int from ,int to);
void leftRotateString(char *s, int length, int num);
int main(void){
char s[] = "asdfqwer";
printf("%s\n",s);
leftRotateString(s, len(s)-1, 3);
printf("%s\n",s);
return 0;
}
void reverseString(char* s, int from ,int to) {
while(from < to) {
char tmp = s[from];
s[from++] = s[to];
s[to--] = tmp;
}
}
void leftRotateString(char *s, int length, int num) {
num = num%length;
reverseString(s,0,num-1);
reverseString(s,num,length-1);
reverseString(s,0,length-1);
}
