字符串循环左移问题
- 1 问题描述:给定一个字符串S[0...N-1],要求把S的前k个字符移到S的尾部,如把S的字符串“abcded"前面的前两个字符“a”,“b”移到字符串的尾部,得到新字符串“cdefab”,即字符串循环左移2位。
- 2 算法要求:时间复杂度为O(n),空间复杂度为O(1)。
- 3 解题思路:三次翻转字符串解法比暴力求解复杂度小,
假设
X='ab'
Y='cdef '
X ' = 'ba'
Y ' = ' fedc '
( X ' Y ' ) ' = ' cdefab
- 4 代码
#include<stdio.h>
void reverseString(char s, int from , int to)
{
while(from<to)
{
char t = s[from];
s[from++] = s[to];
s[to--] = t;
}
}
void leftRotateString(chars, int n, int m)
{
m %= n;
reverseString(s,0,m-1);
reverseString(s,m,n-1);
reverseString(s,0,n-1);
}
int main()
{
char str[] = "abcdef";
printf("The string:%s\n", str);
leftRotateString(str, 6, 2);
printf("After left shift:%s\n", str);
return 0;
} - 5 该问题可作为完美洗牌算法的子算法,未完待续......
网友评论