1.1 旋转字符串

题目描述

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

分析与解法

解法一：暴力移位法

初看此题，可能最先想到的方法是按照题目所要求的，把需要移动的字符一个一个地移动到字符串的尾部，如此我们可以实现一个函数LeftShiftOne(char* s, int n) ，以完成移动一个字符到字符串尾部的功能，代码如下所示：

1
2
3
4
5
6
7
8
9
void LeftShiftOne(char* s, int n)
{
    char t = s[0];  //保存第一个字符
    for (int i = 1; i < n; i++)
    {
        s[i - 1] = s[i];
    }
    s[n - 1] = t;
}

因此，若要把字符串开头的 m 个字符移动到字符串的尾部，则可以如下操作：

1
2
3
4
5
6
7
void LeftRotateString(char* s, int n, int m)
{
    while (m--)
    {
        LeftShiftOne(s, n);
    }
}

下面，我们来分析一下这种方法的时间复杂度和空间复杂度。

针对长度为 n 的字符串来说，假设需要移动 m 个字符到字符串的尾部，那么总共需要 m*n 次操作，同时设立一个变量保存第一个字符，如此，时间复杂度为 O(m * n)，空间复杂度为 O(1)，空间复杂度符合题目要求，但时间复杂度不符合，所以，我们得需要寻找其他更好的办法来降低时间复杂度。

解法二：三步反转法

对于这个问题，换一个角度思考一下。

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

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

  1. 首先将原字符串分为两个部分，即 X:abc，Y:def；
  2. 将 X 反转，X->X^T，即得：abc->cba；将 Y 反转，Y->Y^T，即得：def->fed。
  3. 反转上述步骤得到的结果字符串 X^TY^T，即反转字符串 cbafed 的两部分（cba 和 fed）给予反转，cbafed 得到 defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

代码则可以这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void ReverseString(char* s,int from,int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

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

这就是把字符串分为两个部分，先各自反转再整体反转的方法，时间复杂度为 O(n)，空间复杂度为 O(1)，达到了题目的要求。

举一反三

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <stdlib.h>
void leftRotateString3(char* s,int str_len,int k);
void reverseString(char* s,int from,int to);

int main()
{
    char s[]="abcdefghijklmnopqrst";//更改为链表
    leftRotateString3(s, 20, 3);
    printf("%s\n", s);
    return 0;
}

void reverseString(char* s,int from,int to)
{
    //反转string；更改为反转链表
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void leftRotateString3(char *s, int str_len, int k){
    for(int i = 0;i < str_len/k; i++){
        reverseString(s, k*i, k*i+k-1);
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
void reverseString(char* s,int from,int to);
void LeftRotateString(char* s,int str_len,int m);

int main()
{
    char b[]="Ilovebaofeng";
    LeftRotateString(b, 12, 7);
    printf("%s\n", b);
    return 0;
}

void ReverseString(char* s,int from,int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void LeftRotateString(char* s,int str_len,int m)
{
    m %= str_len;
    m = str_len - m;//将m个字符移到头部相当于将str_len-m个字符移到尾部
    ReverseString(s, 0, m - 1);
    ReverseString(s, m, str_len - 1);
    ReverseString(s, 0, str_len - 1);
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>
void ReverseString(char* s,int from,int to);
void LeftRotateString(char* s,int n);

int main()
{
    char b[]="I am a student.";//字符串长度为15
    //C语言中字符串以字符数组的形式存储
    LeftRotateString(b, 16);//要加上最后的'\0'，所以长度为16
    printf("%s\n", b);
    return 0;
}

void ReverseString(char* s,int from,int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void LeftRotateString(char* s,int n){
    int sum = 0;//单词长度
    int position = 0;//下一个字符串的首字母位置

    for(int i=0;i<n; i++){
        if(sum > 0 && (s[i] == ' ' || s[i] == '\0')){
            ReverseString(s, position, position + sum -1);
            position = position + sum + 1;
            sum = -1;//将sum置0，因为后面还要加1所以是-1
        }
        sum++;
    }
    ReverseString(s, 0, n-2);//字符串最后一个字符下标为字符串长度-1-'\0'
}

优化过的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <string.h>
void ReverseString(char* s,int from,int to);
void LeftRotateString(char* s,int n);

int main()
{
    char b[]="I am a student, and you?";
    LeftRotateString(b, strlen(b));
    printf("%s\n", b);
    return 0;
}

void ReverseString(char* s,int from,int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void LeftRotateString(char* s,int n){
    int sum = 0;
    int position = 0;

    n += 1;
    for(int i=0;i<n; i++){
        if(sum > 0 && (s[i] == ' ' || s[i] == '\0')){
            ReverseString(s, position, position + sum -1);
            position = position + sum + 1;
            sum = -1;
        }
        sum++;
    }
    ReverseString(s, 0, n-2);
}