数据结构与算法学习笔记（7）——字符串

发表于   |   分类于   |  

本章来总结各种有关于字符串的问题。

本文仅供个人记录和复习，不用于其他用途

替换空格

请实现一个函数，将一个字符串中的空格替换成%20。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

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
class Solution
{
public:
    void replaceSpace(char *str,int length)
    {
        int pOldNumber = 0;
        int pNewNumber = 0;
        int newLength = 0;
        int spaceCount = 0;
        int i = 0;
        while(str[i] != '\0')
        {
            if (str[i] == ' ')
            {
                spaceCount++;
            }
            i++;
        }
        newLength = i + spaceCount * 2;
        pOldNumber = i;
        pNewNumber = newLength;
        while(pOldNumber >= 0 && pNewNumber > pOldNumber)
        {
            if(str[pOldNumber] == ' ')
            {
                str[pNewNumber--] = '0';
                str[pNewNumber--] = '2';
                str[pNewNumber--] = '%';
            }
            else
            {
                str[pNewNumber--] = str[pOldNumber];
            }
            pOldNumber--;
        }
    }
};

从前往后替换是不行的，这样一来每次遇到空格，后面的数字都要移动。我们先判断空格数量，确定好长度，然后将前面的数字对应的往后移，如果遇到空格，就替换成%20即可。用这种方法每个数字只要移动一次，效率高很多。

回文字符串

现在给出一个长度不超过1000的字符串，判断它是不是回文(顺读，逆读均相同)的。可能会有多组数据。

回文字符串就是正着看和反着看是一样的，会出现两种可能：

  • 如果字符串长度是偶数，那么前一半要和后一半对称
  • 如果字符串长度是奇数，那么除了中间的一个字符，前一半要和后一半对称

总之，判断回文字符串只需要定义一个栈，将前半部分入栈，然后和后一半逐个对比。如果相等就出栈，最后的栈若为空，那么该字符串便为回文字符串：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
#define MAX 1000
bool charge(char *s)
{
    int length = strlen(s);
    if (length == 2)
    {
        if (s[0] == s[1])
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else if (length == 1)
    {
        return true;
    }
    else
    {
        stack<char> Stack;
        int i;
        for (i = 0; i != length / 2; i++)
        {
            Stack.push(s[i]);
        }
        
        if (length % 2)
        {
            i++;
        }
        
        char temp;
        
        for(; i != length; i++)
        {
            temp = Stack.top();
            if (temp == s[i])
            {
                Stack.pop();
            }
        }
        
        if (Stack.empty())
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}
int main()
{
    char s[MAX];
    while (scanf("%s", &s) != EOF)
    {
        if (charge(s))
        {
            printf("Yes!\n");
        }
        else
        {
            printf("No!\n");
        }
    }
}

查找重复字符

对给定的一个字符串，找出有重复的字符，并给出其位置，如：abcaaAB12ab12 输出：a，1；a，4；a，5；a，10，b，2；b，11，1，8；1，12， 2，9；2，13。

这个题目其实很简单，只需要有两个嵌套循环，针对每一种字符进行检测。这里我用了一种方法，那就是将重复的字符设为‘*’，遇到时直接输出即可。

另外说一下，这个first有两个作用，如果是第一次出现，那么就输出相应的格式。另外，如果这一种字符全部检查完了之后，也可以用作判断换行的时机。

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
40
#include <stdio.h>
#include <string.h>
#define MAX 100
int main()
{
    char s[MAX];
    while (scanf("%s", &s) != EOF)
    {
        int length = strlen(s);
        for (int i = 0; i != length; i++)
        {
            bool first = false;
            if (s[i] == '*')
            {
                continue;
            }
            
            for(int j = i + 1; j != length; j++)
            {
                if (s[i] == s[j])
                {
                    if (!first)
                    {
                        printf("%c:%d", s[i], i);
                        first = true;
                    }
                    printf(",%c:%d", s[j], j);
                    s[j] = '*';
                }
            }
            
            if (first)
            {
                printf("\n");
            }
        }
    }
}

加法计算器

实现一个加法器，使其能够输出a+b的值。输入包括两个数a和b，其中a和b的位数不超过1000位。

由于位数过多，所以我们不能用一般的数据类型。我们可以先用字符串获取输入，然后转换成整型数组。至于相加的部分，就可以按照我们手动计算的步骤进行设计，满十进一即可。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char a[1004], b[1004];
    int t;
    int x[1004], y[1004];
    int answer[1004];
    
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    
    while (scanf("%s%s", a, b) != EOF)
    {
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        memset(answer, 0, sizeof(answer));
        
        int lena = strlen(a);
        int lenb = strlen(b);
        
        for (int i = 0; i < lena; i++)
        {
            x[i] = a[lena - 1 - i] - '0';
        }
        for (int i = 0; i < lenb; i++)
        {
            y[i] = b[lenb - 1 - i] - '0';
        }
        
        int c = 0;
        for (int i = 0; i < lena + 1 || i < lenb + 1; i++)
        {
            answer[i] = (x[i] + y[i] + c) % 10;
            c = (x[i] + y[i] + c) / 10;
        }
        
        int lenans = lena > lenb ? lena : lenb;
        for (int i = lenans - 1; i >= 0; i--)
        {
            if (answer[lenans - 1] == 0)
            {
                continue;
            }
            else
            {
                printf("%d", answer[i]);
            }
        }
        printf("\n");
    }
}

大整数排序

要求：对N个长度最长可达到1000的数进行排序，按照由小到大的顺序输出。

其实这个上面差不多，由于整数过大，我们只能够用字符串来存储，有下面三种情况：

  • 字符串s1长度大于s2，那么s1就比s2大
  • s1长度小于s2，那么s1比s2小
  • 如果相等，那就需要比较每个位置上的数字大小
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
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
static bool comp(string a,string b)
{
    if(a.length() < b.length())
        return true;
    if(a.length() > b.length())
        return false;
    if(a.length() == b.length())
        return a < b;
    return false;
}
int main()
{
    int N;
    while(cin >> N)
    {
        vector<string> vec(N, "");
        for(int i = 0; i < N; i++)
            cin >> vec[i];
        sort(vec.begin(), vec.end(), comp);
         
        for(int i = 0; i < N; i++)
            cout << vec[i] << endl;
    }
    return 0;
}

这里string字符串进行比较时，满足条件则返回值大于0，相等则返回0，不满足则返回值小于0。

另一种A+B

给定两个整数A和B，其表示形式是：从个位开始，每三位数用逗号”,”隔开。 现在请计算A+B的结果，并以正常形式输出。

这个同样是用字符串来存储，然后将字符串转换成整数即可。

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 <iostream>
using namespace std;
int translate(string str)
{
    int temp = 0;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == ',' || str[i] == '-')
        {
            continue;
        }
        else
        {
            temp = temp * 10 + (str[i] - '0');
        }
    }
    
    if (str[0] != '-')
    {
        return temp;
    }
    else
    {
        return -temp;
    }
}
int main()
{
    int a, b;
    string stra, strb;
    while (cin >> stra >> strb)
    {
        a = translate(stra);
        b = translate(strb);
        printf("%d\n", a + b);
    }
}

日历

严格来说这个和字符串没关系，不过经常可能用到，我就拿过来了。现在给你一个年份和天数，你的任务就是输出这个天数是这一年的几月几号。

其实也简单，先判断是闰年还是平年，然后拿总天数减去每月的天数，得出月份即可。

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
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int y, n;
    int month[13] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    while (cin >> y >> n)
    {
        int monnum = 1;
        if (y % 4 == 0 && y % 100 != 0 || y % 400 == 0)
        {
            month[2] = 29;
        }
        else
        {
            month[2] = 28;
        }
        
        for (int i = 1; i <= 12; i++)
        {
            if (n > month[i])
            {
                n -= month[i];
                monnum++;
            }
            else
            {
                break;
            }
        }
        
        printf("%d-%02d-%02d\n", y, monnum, n);
    }
}

字符串匹配

给两个字符串，问第一个字符串中是否包含第二个字符串？

BF算法

这个问题要解决很简单，只需要进行暴力搜索，对第一个字符串进行遍历，当首字符相同时，逐一与第二个字符串对比，不相同则跳转到下一个字符。虽然，方法很简单，不过由于是双层循环，时间复杂度为O(N*M)。

KMP算法

仔细观察暴力搜索方法，我们很容易就能够发现一个缺点：暴力搜索算法没有利用已有的资源。每当算法不匹配时，它都会往后跳一步，但很多时候只跳一步是很浪费时间的，如果能够多跳几步，所花费的时间就会更短，而KMP算法正是基于这个想法。

大致步骤其实和BF算法差不多，只不过，当某处匹配失败时，不再跳转到开始位置的下个字符，而是直接从失败的位置开始匹配，之前匹配成功的字符就不用再比较了。

Horspool算法

这个算法的比较新颖，同样是在第一个字符串中取一个匹配串，拿它和第二个字符串比较，不过是要从右往左比较，例如：

匹配串：abcbcdx...(后面省略)
模板串：cbcac

第一个c-c对比上了，但第二个b-a却不对。那么这时候，模板串从不匹配的位置开始，从右往左寻找是否有字符b。我们发现模版串中有b，所以就把匹配串向右移两位：

匹配串：abcbcdx...(后面省略)
模板串：  cbcac

也就是说，发生不匹配的情况时，从右往左检查模板串中是否存在不匹配的字符，若存在，则移动对应的长度，让两个字符对齐，否则就只能移动整个模板串的长度。

Sunday算法

这个算法和Horspool很像，不过不是去找不匹配的字符，而是直接找匹配串的下一个字符存不存在于模板串，例如：

匹配串：abcbcdxcbc...(后面省略)
模板串：dbcac

我们发现b-a不匹配，然后就找匹配串的下个字符d在不在模板串中。如果在，那么就跳到那个字符的位置：

匹配串：abcbcdxcbc...(后面省略)
模板串：     dbcac

如果没有那个字符，那就跳到那个字符的下一个位置。Sunday算法相比于其他算法，速度够快，而且简单易懂。

判断子树　

问：给定彼此独立的两棵树头节点分别为t1和t2，判断t1中是否有与t2树拓扑结构完全相同的子树。

一般的解法是考察t1中以每个节点为头的子树是否与t2一致，不过如果这么做的话，那就是二叉树的解法了，这里介绍一种更好的方法：首先将t1和t2两棵树转化成字符串str1和str2，判断str1中是否包含str2。

至于如何把二叉树转换为字符串，具体的可以看看二叉树一章。而关于字符串的匹配，可以使用上面介绍的算法。

旋转词

问：给定一个字符串str，把字符串str前面任意的部分挪到后面去形成的字符串叫做str的旋转词。比如str=”1234”，str的旋转词有”1234”、”2341”、”3412”、”4123”。现给定两个字符串a和b，请判断a和b是否互为旋转词。

最优解时间复杂度为O(N)：

  • 判断str1与str2是否长度相等
  • 如果长度相等，生成str1+str1的大字符串
  • 用字符匹配的算法判断大字符串中是否含有str2

我们会发现，在str1+str1中，任意与str1长度相等的字符串都是str1的旋转词。

逆序调整

问：给定一个字符串str，请在单词间做逆序调整

解法如下：

  • 实现一个函数，其功能为将字符串局部的所有字符进行逆序
  • 利用该函数将字符串所有字符逆序
  • 找到逆序后的字符串中每一个单词的区域，利用函数将每一个单词的区域逆序

例如，”Hello World!”进行所有字符逆序，变为”!dlroW olleH”。随后，找到逆序后的字符串中每一个单词的区域，并且将每个单词区域进行逆序，至于单词的区域则可用空格来判断，得到的结果为”World! Hello”。

字符串插入

问：给定一个字符串str，和一个整数i。i代表str中的位置，现将str[0…i]移到右侧，str[i+1…N-1]移到左侧。

解法如下：

  • 将str[0…i]部分的字符逆序
  • 将str[i+1…N-1]部分的字符逆序
  • 将str整体的字符逆序

该题解法与上一题类似，是将各个部分的字符串进行逆序，最后整体进行调整。这种做法只需要单纯地执行逆序操作，无需进行真正意义上的插入。