程序员编程技术学习笔记——左旋转字符串

1.    题目描述

    给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符‘a‘和‘b‘移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

2.    解法1：暴力左移

    这个解法简单粗暴易想！你不是要以为k个字符吗，我先移动一位，然后把移动一位的函数运行k次就好啦~~其中移位1位的程序也好写，取首位字符，转存，后面n-1移位，转存字符放最后，即可。

我们用下面的图示来帮助说明：

这种解法的算法思想和流程步骤我们都说好了。我们来分析一下它的复杂度：时间复杂度O(kn)，空间复杂度O(1)。哎呀，时间太长了！不符合题目的要求，难怪叫做暴力左移……不管怎样，我们还是要给出这种解法的实现代码的。

#include <iostream>

using namespace std;

string leftShift1(string str, int n, int k)
{
    char temp;
    int i;
    while(k--)  //移位k次
    {
        temp=str[0];
        for(i=1; i<n; i++)
        {
            str[i-1]=str[i];
        }
        str[n-1]=temp;
    }
    return str;
}

int main()
{
    string str="abcdef";
    int n=str.length();  //串长
    int k=2;  //需要左移的位数

    if(k>=n) k%=n;  //考虑健壮性
    str=leftShift1(str, n, k);
    cout<<str<<endl;

    return 0;
}

3.  解法2：挥霍空间

    你听这种方法的名字就知道，这种方法的空间复杂度应该比较高。算法其实也很简单：新建一个等长的字符数组strArray，先把前面的k位字符复制到strArray的最后k位，类似复制后面n-k位，即可。

如下图所示：

这种方法的空间复杂度为O(n)，时间复杂度为O(n)，时间复杂度符合要求，当时空间复杂度不行。实现代码如下：

string leftShift2(string str, int n, int k)
{
    string str2="";
    str2=str2+str.substr(k, n-k);  //用到了string类型的+连接和substr取子串
    str2=str2+str.substr(0, k);
    return str2;
}

4.    解法3：手摇法

    这种叫做手摇法，那么什么是手摇法呢？july博客上给出了图示：

很神奇吧~~这个过程是不是和字符串翻转很像呢~

    上面这个过程数学化为：

    将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。

    例如，字符串 abcdef ，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可：

    首先将原字符串分为两个部分，即X:abc，Y:def；

    将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。

    反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

    我们也用下面的图示说明：

    反转的过程也较简单，例如从head到tail是需要反转的字符串，我们先把head给temp，然后tail给head，head++，temp给tail，tail--，一直运行到head>tail即可。

    由此可见，该方法的空间复杂度为O(1)，时间复杂度为O(n+n)=O(n)。为啥是O(n+n)呢？因为这里有3次反转，前两次加起来为O(n)，第三次是全部长度反转，为另一个O(n)，这样即可。

    下面我们给出代码：

string ReverseString(string str,int head,int tail)
{
    while (head < tail)
    {
        char t = str[head];
        str[head++] = str[tail];
        str[tail--] = t;
    }
    return str;
}


string leftShift3(string str, int n, int k)
{
    k %= n;               //若要左移动大于n位，那么和%n 是等价的
    str=ReverseString(str, 0, k - 1); //反转[0..k - 1]，套用到上面举的例子中，就是X->X^T，即 abc->cba
    str=ReverseString(str, k, n - 1); //反转[k..n - 1]，例如Y->Y^T，即 def->fed
    str=ReverseString(str, 0, n - 1); //反转[0..n - 1]，即如整个反转，(X^TY^T)^T=YX，即 cbafed->defabc。
    return str;
}

5.    举一反三

    1）、链表翻转。给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。

    2）、编写程序，在原字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。

    3）、单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”。