旋转字符串，加了算法解释，求验证——总结：空间的处理，内、外空间都可以利用

cokeboL

1. #include <cstdio>
   
2. #include <string.h>
   
3. 
   
4. int timeCount = 0;
   
5. 
   
6. //len为需要转换的总长度，n是旋转的长度
   
7. void str_turn_left(char *src, int len, int n)
   
8. {
   
9.         int i, end = len - 1;
   
10.         char tmp;
    
11. 
    
12.         n = n % len;
    
13.         if(0 == (len * n))
    
14.                 return;
    
15. 
    
16.         while(end >= n - 1){
    
17.                 for(i = n-1; i >= 0; i--, end--){
    
18.                                                 timeCount++; //时间复杂度计数
    
19.                         tmp = src[end];
    
20.                         src[end] = src[i];
    
21.                         src[i] = tmp;
    
22.                 }
    
23.         }
    
24.         if((len % n) > 1)
    
25.                 str_turn_left(src, len % n, n%(len % n));
    
26. }
    
27. 
    
28. 
    
29. int main()
    
30. {
    
31.         int i;
    
32. 
    
33.         char a[15][20] =
    
34.         {
    
35.                 "a",
    
36.                 "ab",
    
37.                 "abc",
    
38.                 "abcd",
    
39.                 "abcde",
    
40.                 "abcdef",
    
41.                 "abcdefg",
    
42.                 "abcdefgh",
    
43.                 "abcdefghi",
    
44.                 "abcdefghij",
    
45.                 "abcdefghijk",
    
46.                 "abcdefghijkl",
    
47.                 "abcdefghijklm",
    
48.                 "abcdefghijklmn",
    
49.                 "abcdefghijklmno",
    
50.         };
    
51. 
    
52.         for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
    
53.                 printf("%s ", a[i]);
    
54. 
    
55.                 str_turn_left(a[i],strlen(a[i]),13);
    
56. 
    
57.                 printf("-> %s\n", a[i]);
    
58.                                 printf("timeCount: %d\n", timeCount);
    
59.                                 timeCount = 0;
    
60.         }
    
61. 
    
62.         return 0;
    
63. }

复制代码

解释下算法：


把字符串按照旋转的长度n分成几段，字符串头的前n个记为1，后面往前数依次为-1、-2，此图举例，到-3段时与1段有交叉；
算法依次按后续调换1段和-1段、1段和-2段、1段和-3段。。。类推；
每次调换-m段时-m段被放到1段的位置，下次和-（m-1）段调换，循环之后从后面数的段依次向前移动了n个字节，并且第一段在第一次调换时已经放在字符串尾部；
最后一次调换，就是第一段和图中-3段调换有交叉或者临界的情况，类似于memmove函数，由于是从后往前调换，可知交叉部分最后被放到了头部，交叉部分之前的部分被调换到了之后的位置，比如 "abcde",用后3个字符“cde”调换前3个字符“abc”之后，变成了“edabc”，这时需要再把'e'和'd'调换，就是旋转交叉部分前面的字符串；
通用的公式: 再次旋转的长度就是1段的长度减去交叉部分的长度，即strlen % n，旋转的位数就是交叉部分的长度，即 n % (len % n)，当len % n <= 1时不交叉或者为单字符，不需要旋转，详见代码

总的来讲，用一个字节进行段的替换，使字符串开头的段成了临时的buf用来存储下次需要调换的字节，这样用1个字节+自身空间实现，节省了单独开辟buf的内存，使空间复杂度为O(1)go，如果不可以，那就随意吧，如果不是cpu消耗型的，性能问题不大，如果用5.1的话可以把luajit搞上比lua快很多

cokeboL

有效代码15行左右，还算俭省；
加打印计算循环次数基本都是  小于等于 strlen，不知道可不可以算时间复杂度为O(<=n)；
循环内的操作，看上去是每次swap交换比较浪费，但实际就相当于几次赋值，与之前那两种经典算法中给下标赋值或者reverse等操作相比，并不浪费；
验证了几个旋转长度1、2、3、5、6、7、13等，目测应该是正确的，但还不敢保证全对；
求各位帮忙验证一下。
那两种经典算法参考：
http://www.cnblogs.com/jy02414216/archive/2012/08/10/2633041.html

shang2010

毕业多年了，一把老骨头了，很少写工作不实用的代码了


google snprintf
这个库函数可是我第一家公司学来的三大利器之一哦{:3_188:}

cokeboL

回复 3# shang2010


简单的字符串操作，何必用snprintf。。。

这个是实现时间O(n)空间O(1)的。。。工作确实不用，只是最近闲的无聊，才玩玩的

cokeboL

回复 5# Sevk


我写这个的初衷是基于之前小乔那个帖子
http://bbs.chinaunix.net/thread-4056843-1-1.html

只考虑O(n) + O(1)情况的算法，两行代码差不多搞定的写法大部分人都懂但是空间做不到O(1)

wk-sky

看这代码感觉费劲，你们是怎么炼就出来的！

sacry

@@

代码删除

cokeboL

回复 9# sacry


    这不就是公约数那个吗，链接里有，我写的是新的，跟那两种不同的，求PK的版本