《算法笔记》3.6小节——入门模拟->字符串处理

问题 A: 字符串连接

题目

题目描述

不借用任何字符串库函数实现无冗余地接受两个字符串，然后把它们无冗余的连接起来。

输入

每一行包括两个字符串，长度不超过 100。

输出

可能有多组测试数据，对于每组数据， 不借用任何字符串库函数实现无冗余地接受两个字符串，然后把它们无冗余的连接起来。 输出连接后的字符串。

样例输入

1
abc def

样例输出

1
abcdef

题解

思路

这题用string类，然后直接输出就好了，简单粗暴。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    string s1, s2;
    while (cin >> s1 >> s2)
    {
        cout << s1 << s2 << endl;
    }

    system("pause");
    return 0;
}

问题 B: 首字母大写

题目

题目描述

对一个字符串中的所有单词，如果单词的首字母不是大写字母，则把单词的首字母变成大写字母。 在字符串中，单词之间通过空白符分隔，空白符包括：空格(' ')、制表符(')、回车符(')、换行符('')。

输入

输入一行：待处理的字符串（长度小于 100）。

输出

可能有多组测试数据，对于每组数据， 输出一行：转换后的字符串。

样例输入

1
if so, you already have a google account. you can sign in on the right.

样例输出

1
If So, You Already Have A Google Account. You Can Sign In On The Right.

题解

思路

这题的思路还是蛮清晰的，思路就是遍历字符串的每个字符，如果当前字符是分隔符且下个字符是小写字符，那么就把下个字符变成大写字符。

代码

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
#include <stdio.h>
#include <iostream>
#include <string.h>

using namespace std;

int main()
{
    char a[100];
    while (cin.getline(a, 100))
    {
        int i = 0;
        if (a[i] >= 'a' && a[i] <= 'z')
        {
            a[i] = a[i] - 32;
        }
        for (i = 1; a[i] != '\0'; i++)
        {
            if (a[i] == ' ' || a[i] == '\t' || a[i] == '\r')
            {
                if (a[i + 1] >= 'a' && a[i + 1] <= 'z')
                {
                    a[i + 1] = a[i + 1] - 32;
                }
            }
        }
        printf("%s\n", a);
    }
    system("pause");
    return 0;
}

问题C：字符串的查找删除

题目

题目描述

给定一个短字符串（不含空格），再给定若干字符串，在这些字符串中删除所含有的短字符串。

输入

输入只有 1 组数据。 输入一个短字符串（不含空格），再输入若干字符串直到文件结束为止。

输出

删除输入的短字符串（不区分大小写）并去掉空格，输出。

样例输入

1
2
3
4
5
6
7
in
#include 
int main()
{

printf(" Hi ");
}

样例输出

1
2
3
4
5
6
#clude
tma()
{

prtf("Hi");
}

提示

注：将字符串中的 In、IN、iN、in 删除。

题解

思路

这题思路比较简单，但是细节处理很重要，提交好几次错了好几次，以下写一下注意事项：

  • 短字符串只有一个，因此使用一个string类对象即可，以下未知个数字符串使用string类数组即可；
  • 因为题目要求去除空格并且去除字符串的时候要忽略大小写，所以全部转换成小写或者大写然后在删除是个容易想到的 idea。我的解法就是先去除空格，然后用另一个string类数组保存一下输入的内容，接着对拷贝的内容字母部分全部小写；
  • 最后在对备份的数组遍历，使用find函数查找短字符串，记录出现的位置，然后使用erase函数删除出现的短字符串即可。

使用到的关于字符串的函数：

  • tolower()：把给定的字母转换为小写字母。

    1
    2
    3
    int tolower(int c);
    // c：要被转换为小写的字母
    // 返回值：如果 c 有相对应的小写字母，则该函数返回 c 的小写字母，否则 c 保持不变。返回值是一个可被隐式转换为 char 类型的 int 值。

    C 标准库 – | 菜鸟教程 (runoob.com)

  • getline()：此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。

    由于cin.getline()函数无法输入string对象，所以需要使用getline()函数。

    1
    2
    istream & getline(char* buf, int bufSize);
    istream & getline(char* buf, int bufSize, char delim);

    C++ getline函数用法详解 (biancheng.net)

    C++ getline()：从文件中读取一行字符串 (biancheng.net)

  • erase()：可以删除指定位置的字符串，删除指定长度的字符串跟删除指定范围的字符串。

    1
    2
    3
    4
    5
    6
    7
    iterator erase (iterator p);
    // 参数 iterator 是迭代器，即删除迭代器 p 指向的字符。返回值为删除后的字符串。
    string& erase(size_t pos=0, size_t len = npos);
    // 参数 pos 表示要删除字符串的起始位置，其默认值是 0;
    // len 表示要删除字符串的长度，其默认值是 string::npos。返回值是删除后的字符串。
    iterator erase (iterator first, iterator last);
    // first 和 last 分别表示范围的起点和终点。需要注意的是，该范围包含 first，但是不包含 last，即该范围是 [first, last)。erase() 函数的返回值是删除后的字符串。

    C++中string类型的erase()函数详解_hou09tian的博客-CSDN博客_string的erase函数

  • find()：在给定字符串中搜索子字符串或字符。

  • 方法原型 描述
    size_type find(const string & str, size_type pos = 0) const 从字符串的 pos 位置开始，查找子字符串 str。如果找到，则返回该子字符串首次出现时其首字符的索引；否则，返回 string::npos
    size_type find(const char * s, size_type pos = 0) const 从字符串的 pos 位置开始，查找子字符串 s。如果找到，则返回该子字符串首次出现时其首字符的索引；否则，返回 string::npos
    size_type find(const char * s, size_type pos = 0, size_type n) const 从字符串的 pos 位置开始，查找 s 的前 n 个字符组成的子字符串。如果找到，则返回该子字符串首次出现时其首字符的索引；否则，返回 string::npos
    size_type find(const char ch, size_type pos = 0) const 从字符串的 pos 位置开始，查找字符 ch。如果找到，则返回该子字符串首次出现的位置；否则，返回 string::npos

    string类的find()函数总结__Previous的博客-CSDN博客_string的find函数

代码

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
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    string str = "";
    getline(cin, str);
    for (int i = 0; i < str.length(); i++)
    {
        str[i] = tolower(str[i]);
    }
    string in[100] = {""};
    int num = 0;
    while (getline(cin, in[num]))
    {
        num++;
    }
    for (int i = 0; i < num; i++)
    {
        while (in[i].find(" ") != -1)
        {
            in[i].erase(in[i].find(" "), 1);
        }
    }
    string temp[100] = {""};
    for (int i = 0; i < num; i++)
    {
        temp[i] = in[i];
        for (int j = 0; j < temp[i].length(); j++)
        {
            if (temp[i][j] >= 'A' && temp[i][j] <= 'Z')
            {
                temp[i][j] = tolower(temp[i][j]);
            }
        }
    }
    for (int i = 0; i < num; i++)
    {
        while (temp[i].find(str) != -1)
        {
            in[i].erase(temp[i].find(str), str.length());
            temp[i].erase(temp[i].find(str), str.length());
        }
        cout << in[i] << endl;
    }

    system("pause");
    return 0;
}

问题 D: 单词替换

题目

题目描述

输入一个字符串，以回车结束（字符串长度<=100）。该字符串由若干个单词组成，单词之间用一个空格隔开，所有单词区分大小写。现需要将其中的某个单词替换成另一个单词，并输出替换之后的字符串。

输入

多组数据。每组数据输入包括 3 行，

第 1 行是包含多个单词的字符串 s，

第 2 行是待替换的单词 a，(长度<=100)

第 3 行是a将被替换的单词 b。(长度<=100)

s, a, b 最前面和最后面都没有空格。

输出

每个测试数据输出只有 1 行，

将s中所有单词 a 替换成 b 之后的字符串。

样例输入

1
2
3
I love Tian Qin
I
You

样例输出

1
You love Tian Qin

题解

思路

[Codeup] 问题 D: 单词替换_ECNUACRush的博客-程序员宝宝 - 程序员宝宝 (cxybb.com)

这题的话，可以不用替换，找到单词 a 的位置就输出单词 b 就好。具体的思路就是遍历第一个字符串 s，然后如果当前下标值i == s.find(a, i)那么说明此时找到了 a，就输出 b，然后 i 要往后移动a.lentgh()个位置；否则照常输出。最后再输出一个空行。

代码

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 <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int main()
{

    string aa, sub, New;
    while (getline(cin, aa))
    {

        cin >> sub >> New;
        getchar(); //清除缓存区的'\n'
        for (int i = 0; i < aa.size();)
        {
            if (i != aa.find(sub, i)) // 从当前位置开始查，若未遍历到欲替换的子串
                cout << aa[i++];      // 直接输出并让i++，输出原串
            else
            {
                //到了该替换的地方，先输出新串，再完成i滑动
                cout << New;
                i += sub.length();
            }
        }
        cout << endl;
    }
    return 0;
}

问题 E: 字符串去特定字符

题目

题目描述

输入字符串 s 和字符 c，要求去掉 s 中所有的 c 字符，并输出结果。

输入

测试数据有多组，每组输入字符串 s 和字符 c。

输出

对于每组输入，输出去除 c 字符后的结果。

样例输入

1
2
goaod
a

样例输出

1
good

题解

思路

这题的思路很简单，但是有几个需要注意的细节：

  • 由于字符串中可能含有空格，于是需要使用getline()函数，这里需要注意，之后我们使用scanf()函数读取了字符c，之后输入的回车也会被下次getline()函数读取，因此在之后需要添加一个getchar()读取缓冲区的回车。
  • 具体思路就是：遍历 s，遇到 c 不输出，否则输出。

代码

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
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    string s;
    while (getline(cin, s))
    {
        char c;
        scanf("%c", &c);
        getchar();
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] != c)
            {
                printf("%c", s[i]);
            }
        }
        printf("\n");
        s = "";
    }

    system("pause");
    return 0;
}

问题 F: 数组逆置

题目

题目描述

输入一个字符串，长度小于等于 200，然后将数组逆置输出。

输入

测试数据有多组，每组输入一个字符串。

输出

对于每组输入，请输出逆置后的结果。

样例输入

1
tianqin

样例输出

1
niqnait

提示

注意输入的字符串可能会有空格。

题解

思路

直接使用algorithm头文件里的reverse()函数就好啦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>

using namespace std;

int main()
{
    string s;
    while (getline(cin, s))
    {
        reverse(s.begin(), s.end());
        cout << s << endl;
    }

    system("pause");
    return 0;
}

问题 G: 比较字符串

题目

题目描述

输入两个字符串，比较两字符串的长度大小关系。

输入

输入第一行表示测试用例的个数m，接下来m行每行两个字符串A和B，字符串长度不超过50。

输出

输出m行。若两字符串长度相等则输出A is equal long to B；若A比B长，则输出A is longer than B；否则输出A is shorter than B。

样例输入

1
2
3
2
abc xy
bbb ccc

样例输出

1
2
abc is longer than xy
bbb is equal long to ccc

题解

思路

比较lena与lenb即可，不知道为啥做差就错了，绝绝子。

代码

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 <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    int count;
    scanf("%d", &count);
    for (int i = 0; i < count; i++)
    {
        char s1[100] = "", s2[100] = "";
        scanf("%s %s", s1, s2);
        int lena = strlen(s1), lenb = strlen(s2);
        if (lena == lenb)
        {
            (i == count - 1) ? printf("%s is equal long to %s", s1, s2) : printf("%s is equal long to %s\n", s1, s2);
        }
        else if (lena > lenb)
        {
            (i == count - 1) ? printf("%s is longer than %s", s1, s2) : printf("%s is longer than %s\n", s1, s2);
        }
        else
        {
            (i == count - 1) ? printf("%s is shorter than %s", s1, s2) : printf("%s is shorter than %s\n", s1, s2);
        }
    }

    system("pause");
    return 0;
}

问题H：编排字符串

题目

题目描述

请输入字符串，最多输入4 个字符串，要求后输入的字符串排在前面，例如

输入：EricZ

输出：1=EricZ

输入：David

输出：1=David 2=EricZ

输入：Peter

输出：1=Peter 2=David 3=EricZ

输入：Alan

输出：1=Alan 2=Peter 3=David 4=EricZ

输入：Jane

输出：1=Jane 2=Alan 3=Peter 4=David

输入

第一行为字符串个数m，接下来m行每行一个字符床，m不超过100，每个字符床长度不超过20。

输出

输出m行，每行按照样例格式输出，注意用一个空格隔开。

样例输入

1
2
3
4
5
6
5
EricZ
David
Peter
Alan
Jane

样例输出

1
2
3
4
5
1=EricZ
1=David 2=EricZ
1=Peter 2=David 3=EricZ
1=Alan 2=Peter 3=David 4=EricZ
1=Jane 2=Alan 3=Peter 4=David

提示

1

题解

思路

本题遇到了先进先出，因此考虑到队列，使用 STL 中的queue。之后在代码中发现需要访问队尾元素，然后队尾元素弹出，但是queue不可以，于是想到双端队列deque，使用deque就很方便解决问题了。

我们控制队列长度为 4，如果输入的 超过了 4，那么弹出队首元素，再在队尾插入。每次输入之后我们都进行输出操作，使用一个临时队列，进行输出弹出操作。

代码

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
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <deque>

using namespace std;

int main()
{
    // 先进先出，考虑长度为4的队列
    deque<string> q;
    int count = 0;
    cin >> count;
    getchar();
    for (int i = 0; i < count; i++)
    {
        string temp;
        getline(cin, temp);
        if (q.size() == 4)
        {
            q.pop_front();
            q.push_back(temp);
        }
        else
        {
            q.push_back(temp);
        }
        int index = 1;
        deque<string> t = q;
        while (t.size() > 0)
        {
            if (index == 1)
            {
                cout << index << "=" << t.back();
                t.pop_back();
            }
            else
            {
                cout << " " << index << "=" << t.back();
                t.pop_back();
            }
            index++;
        }
        cout << endl;
    }

    system("pause");
    return 0;
}

问题I：【字符串】回文串

题目

题目描述

读入一串字符，判断是否是回文串。“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

输入

一行字符串，长度不超过255。

输出

如果是回文串，输出“YES”，否则输出“NO”。

样例输入

1
12321

样例输出

1
YES

题解

思路

回文串很基础的题目了，直接干。

代码

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 <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    string s;
    while (cin >> s)
    {
        int i = 0;
        for (; i < s.length() / 2; i++)
        {
            if (s[i] != s[s.length() - i - 1])
            {
                break;
            }
        }
        if (i == s.length() / 2)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }

    system("pause");
    return 0;
}
#算法 #算法笔记
《算法笔记》3.6小节——入门模拟->字符串处理
https://excelius.xyz/《算法笔记》3-6小节——入门模拟-字符串处理/
作者
Excelius
发布于
2022年1月16日
许可协议