编程珠玑-第二章（字符串旋转与排序）

我会带着你远行 2022-09-23 05:59 212阅读 0赞

关于字符串旋转的一些想法  
注意：区别字符旋转和字符串倒序排列的区别，旋转为abcd-》cdad  
1.杂耍算法  
特点：可以在空间有限的情况下解决问题，但是缓存性能差。

#include <iostream>
    #include <assert.h>
    using namespace std;
    
    /*获取m和n的最大公约数*/
    int GCD(int m,int n)
    {
        int tmp;
        if (m < n)
        {
            tmp = m;
            m = n;
            n = tmp;
        }//调整数字大小顺序
        if (m % n == 0)
        {
            return n;
        }
        else
        {
            return GCD(n,m%n);//此处使用的是辗转相除法来求最大公约数
        }
    }
    
    
    void RotateString(char* str,int k)
    {
        assert(str != NULL && k > 0);
        int strLen = strlen(str);
        int GCDNum = GCD(strLen,k);
    
        for (int i = 0;i < GCDNum;i++)//最大公约数即是循环的次数
        {
            int first = i;
            int next = (first + k) % strLen;
            char tmp = str[i];
    
            while(next != i)//移位停止的条件是当下一个元素移位回到起始点
            {
                str[first] = str[next];
                first = next;
                next = (first + k) % strLen;
            }
            str[first] = tmp;//临时存储的变量最后单独赋值
        }
    }
    
    int main()
    {
    
        char str[30] = "abcdef";
        RotateString(str,3);
        cout<<str<<endl;
        return 0;

2.可以使用求逆的方式  
将总字符分成两个部分，先分别倒排，再整体倒排一次。例如12345-32145-32154-45123

reverse(0,i-1);
    reverse(i,n-1);
    reverse(0,n-1);

void reverse(char* str,int start,int end)
    {
        char temp;
        int mid = (start + end)/2;
        for(int i = start,int j = end;i < = mid;i++,j++)
        {
            temp = str[start];
            str[start] = str[end];
            str[end] = temp;
        }
    }

3.块交换，首先将额外使用一块内存（一个临时数组），将要交换的块1进行一个拷贝，在块2变换之后，将块1拷贝放回。  
参考：[http://www.cnblogs.com/solidblog/archive/2012/07/18/2596683.html][http_www.cnblogs.com_solidblog_archive_2012_07_18_2596683.html]

[http_www.cnblogs.com_solidblog_archive_2012_07_18_2596683.html]: http://www.cnblogs.com/solidblog/archive/2012/07/18/2596683.html