life02
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  197 随笔 :: 3 文章 :: 37 评论 :: 0 Trackbacks
字符串循环移位 - 编程珠玑的一道题(转)
// 编程珠玑 第二章 字符串string循环移位i位
// eg "abcdefgh" 循环移位 3位 =》 "defghabc"
#include<iostream.h>
#include <string.h>

char* string_cyclicshift_v2( char* string, int i )
{
    char ch;
    int exchange;
    int len;
    
    exchange = 0;
    len = strlen( string );
    
    i = i%len;
    if ( 0 == i )
        return string;
    
    int start_pos=0;
    while ( exchange<len )
    {
        char ch = string[start_pos];
        
        int currpos = start_pos;
        int nextpos = (len+currpos+i)%len;
        while ( nextpos != start_pos )
        {
            string[currpos] = string[nextpos];
            ++exchange;
            
            currpos = nextpos;
            nextpos = (len+currpos+i)%len;

        }
         cout<<string<<endl;
        string[currpos] = ch;
        ++exchange;
        
        ++start_pos;
    }
    
    return string;
}

int main(){
    char string[7]={'a','b','h','d','h','s'};
    cout<<string<<endl;
    char* s;
    s=string_cyclicshift_v2(string,4);
    cout<<s<<endl;

return 0;
}

要求时间复杂度空间复杂度都尽可能的低。

时间复杂度 O（n）, 空间复杂度O（1），常量时间。

http://blog.csdn.net/zdl1016/archive/2009/09/21/4575309.aspx
posted on 2009-09-28 23:02 life02 阅读(1180) 评论(1)  编辑 收藏 引用 所属分类: 算法

评论

# re: 字符串循环移位 - 编程珠玑的一道题(转)[未登录] 2011-01-14 20:31 yy
for (int i = 0; i < str_len; i++)
new_str[i] = old_str[(i+offset)%len];  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理