左旋字符串求助

定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。

我的解法是这样的：

1. 
   
2. void spin(char *str, int i, int j){
   
3. 
   
4. while(1){
   
5.     if(str == 0||*(str+j+1)=='\0')           break;
   
6.     if(j<i) break;
   
7.     if((j-i+1)>strlen(str+j+1)){
   
8.         int p = i, q=j+1;
   
9.         char temp;
   
10.         while(*(str+q)!='\0'){
    
11.             temp = *(str+p);
    
12.             *(str+p) = *(str+q);
    
13.             *(str+q) = temp;
    
14.             p++;
    
15.             q++;
    
16.         }
    
17.         i =p;
    
18.     }else{
    
19.         int p = i, q=j+1;
    
20.         char temp;
    
21.         while(p<=j&&*str+q!='\0'){
    
22.             temp = *(str+p);
    
23.             *(str+p) = *(str+q);
    
24.             *(str+q) = temp;
    
25.             p++;
    
26.             q++;
    
27.         }
    
28.         i=p;
    
29.                 j=q-1;
    
30.     }
    
31.         }
    
32. 
    
33. }

复制代码

请问只是O（n）的解法吗？

递归…… 空间复杂度…… 呃……

你是要练习指针的使用？给个麻烦的解法：

解法（数组）:
int main()
{
    string str;
    int str_len;
    int left_move;
    char * ptr;
    cin>>str;
    str_len = strlen(str);
    cin>>left_move;
    ptr = (&str+left_move);
    for (int i = left_move; i<str_len; i++)
    {
        cout<< *(&str+i);
    }
    for (int j = 0; j<left_move; j++)
    {
        cout<< *(&str+j);
    }
}

annielife 发表于 2012-11-11 22:08
你是要练习指针的使用？给个麻烦的解法：

解法（数组）:

你这个不行。。 只是输出，要求是转换成另外一个字符串，并且要求时间空间，空间复杂度。

Henry1324 发表于 2012-11-11 21:48
递归…… 空间复杂度…… 呃……

你说的对，不能用递归。。 忘了这茬了。。。

Henry1324 发表于 2012-11-11 21:48
递归…… 空间复杂度…… 呃……

现在呢？ 改成不用递归的了。思路是这样的abcdef -> cdabef -〉cdefab,  我计算时间复杂度是设要移动的字符串长度为m，总长为n， 那么需要操作的次数是（n/m-1）*m = n-m;  所以我觉得应该是个时间复杂度为n的解法。 不过还不是很确定，所以发上来和大家讨论下

lhy1987 发表于 2012-11-12 05:10
现在呢？ 改成不用递归的了。思路是这样的abcdef -> cdabef -〉cdefab,  我计算时间复杂度是设要移动的字 ...

学识有限 真心看不懂这些i j k变量名……

lhy1987 发表于 2012-11-12 04:56
你这个不行。。 只是输出，要求是转换成另外一个字符串，并且要求时间空间，空间复杂度。

那就把输出改成存到另外一个string里面应该就可以了，其实是一回事

annielife 发表于 2012-11-12 19:14
那就把输出改成存到另外一个string里面应该就可以了，其实是一回事

空间复杂度。。。

Henry1324 发表于 2012-11-12 14:55
学识有限 真心看不懂这些i j k变量名……

谢谢，写得不好，不详细，不规范。 勿怪