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

Bertha 。 2022-08-14 03:47 175阅读 0赞

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

# **1. 题目描述** #

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

# **2. 解法1：暴力左移** #

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

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

![Center][]

这种解法的算法思想和流程步骤我们都说好了。我们来分析一下它的复杂度：时间复杂度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位，即可。

如下图所示：

![Center 1][]

这种方法的空间复杂度为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博客上给出了图示：

![Center 2][]

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

上面这个过程数学化为：

将一个字符串分成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，这就实现了整个反转。

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

![Center 3][]

反转的过程也较简单，例如从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”。

最后给出july的链接：

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md

[Center]: /images/20220810/104e117984c34f90a642b57120063dcb.png
[Center 1]: /images/20220810/69f52191004042f88d47c2553acdd364.png
[Center 2]: /images/20220810/fb36c9abb8084f49a12e088f8c5ff731.png
[Center 3]: /images/20220810/93ddc14dd0c2410a9be2dd19df1130ba.png