浅谈左移算法

Posted on | In | | Visitors:

假设有一个字符串”abcdefgh”，循环左移3位后得到”defghabc”，本文讲解其中的一种左移算法。

已知条件如下：

  • 目标字符串（x）：abcdefgh
  • 字符串长度（n）：8
  • 循环左移位数（l）：3
  • 预期结果（y）：defghabc

先考虑左移一位的情况，这个算法可以这样设计：

  • 将第一个字符x[0]暂存到变量t，然后x[1]赋给x[0]，x[2]赋给x[1]，以此类推
  • 结束条件为：x[i]的i等于n（即8），将t赋给x[n-1]（即x[7]）

结束条件的特点是：x[i]的i对n做模运算等于缓存t时的字符数组下标（即0），继续归纳左移二位的情况：

  • x[0]赋给t，x[2]赋给x[0]，以此类推，结束条件同上，结束时t赋给x[6]
  • 然而x[1]，x[3]，x[5]，x[7]的位置是错的，按照上述规则执行一次移位，左移二位的工作全部完成

这里的特点是n（即8）是l（即2）的倍数。第一次执行移位时，有4个字符的位置正确；第二次移位时，另外4个字符的位置也正确了，移位完成。这里可以归纳出来的结论是：移位的次数为n与l的最大公约数。

因此，对于上文已知条件的求解，只需要按照上述算法执行一趟即可完成移位。算法的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
# gcd为最大公约数计算
for i in [0, gcd(n, l)):
    t = x[i]
    j = i
    while true:
        k = (j + l) % n
	if k == i:
	    break
	x[j] = x[k]
	j = k
    x[j] = t

注：

  1. 算法整理自《编程珠玑2》
  2. 还有一种思路是：将字符串存储在一个循环链表中，然后偏移index指针到开始位置，按顺序进行读取即可，但比上述算法耗费空间（每个字符需要持有两个指针，一个指向前，一个指向后）