字符串循环移位(2次翻转的思路)

给定一个字符串S[0…N-1],要求把S的前k个字符移动到S的尾部,如把字符串“abcdef”前面的2个字符‘a’、‘b’移动到字符串的尾部,得到新字符串“cdefab”:即字符串循环左移k。

算法要求: 时间复杂度为 O(n),空间复杂度为 O(1)。

利用翻转两次的算法思路:

假设字符串长度为n , 循环移动k次,那么相当于移动 k%n

1、先将前k%n位翻转,再将后n-k%n翻转

2、总体再翻转。

例如:

abcdef   左移2位 得到cdefab

1、ab翻转得到ba   cdef翻转fedc

2、整体翻转 cdefab

abcdef 左移10位 得到 efabcd

1、abcd翻转得到dcba ef翻转得到fe

2、整体翻转得到 efabcd

如果是循环右移的话:

假设字符串长度为n, 循环右移k位,那么相当于移动k%n位

1、先将前n-k%n翻转,再将后k%n翻转

2、再整体翻转

例如 

abcdef 右移2位得到 efabcd 

1、先翻转 abcd得到dcba , 再翻转ef得到 fe

2、再整体翻转得到efabcd

右移8位置得到efabcd

1、先翻转6-2 位 abcd得到dcba ,再翻转ef得到fe

2、再整体翻转得到efabcd

原文地址:https://www.cnblogs.com/wsw-seu/p/13629719.html