记录天梯赛训练碰到的问题

字符串

输入空格

C++中

scanf()函数读字符，空格成功读入，碰到回车，tab，空格结束

cin读string，空格全部跳过，最后碰到回车结束

输入样例:

programming is More fun!

m

输出样例:

2

最后一个测试点只有一个空格，所以我一开始用cin函数输入失败了

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<iostream>

using namespace std;

const int defaultSize = 1000;

int lst[130] = { 0 };
char result;

void Init()
{
	char temp = '0';
	while (1)
	{
        //scanf_s("%c", &temp);
		scanf("%c", &temp);
		if (temp == '\n')
		{
			break;
		}
		lst[temp]++;
	}
    //scanf_s("%c", &result);
	scanf("%c", &result);
}

int main()
{
	Init();
	cout << lst[(int)result];
}

最后一个测试点是只有一个空格，参考PTA 实验7-3-8 统计字符出现次数


我用的是输入一个一个字符的方法，也可以直接读取这个字符串再处理

C++中如果要输入带空格的字符串，可以用cin.getline()函数，也可以用<stdio.h>中gets()函数

cin.getline(char* s, int count, char end)

s为字符数组，count为读取个数，end为结束字符，如果不写end则碰到回车结束，所以可以用这个函数读带空格的字符串

读入的字符串结尾字符为'\0'

1
2
3
char s1[1000];
cin.getline(s1, 1000);
cout << s1;

也可以带<string>头文件，这样可以用string自带的函数，比如length()，find()等

getline(cin, string str)

第一个参数是cin，第二个参数直接带string类型就好

1
2
3
string str;
getline(cin,str);
cout << str;


参考ACM小练习之字符串的处理

汉字字符串

UTF-8，一个汉字占2个字节

1
2
string a = "测试abc";
cout << a.length();

输出为7

1
2
3
4
5
6
string a = "测试abc";
char c[3];
c[0] = a[0];
c[1] = a[1];
c[2] = '\0';
cout << c;

输出为测

这样就有了截取字符串中汉字的方法，即用一个长度为3的char数组，前2个元素存对应汉字对应字节，最后一个元素存'\0'，可以保证字符串正常输出

但是把这样的解决方法提交到PTA中，发现失败了

PTA中提示说一个汉字3个字节，把字符数组长度重新调整为4，一个汉字的3个字节重新交一下，发现成功过了全部测试点，挺怪的

输入样例：

悠悠田园风 然而心难平 兰花轻涌浪 兰香愈幽静

输出样例：

风平浪静


以下是成功通过PTA的代码，可能因为编码方式不同，本机跑一个汉字2个字节

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>

using namespace std;

const int defaultSize = 1000;

string lst[5];

void Init()
{
	for (int i = 0; i < 4; i++)
	{
		cin >> lst[i];
	}
}

void Print_PTA()	//PTA中测试，一个汉字3个字节
{
	char result[4];
	result[3] = '\0';
	for (int i = 0; i < 4; i++)
	{
		int len = lst[i].length();
		result[2] = lst[i][len - 1];
		result[1] = lst[i][len - 2];
		result[0] = lst[i][len - 3];
		cout << result;
	}
	cout << endl;
}
void Print()		//本机测试，输入的一个汉字2个字节，应该是编码方式不一样
{
	char result[3];
	result[2] = '\0';
	for (int i = 0; i < 4; i++)
	{
		int len = lst[i].length();
		result[1] = lst[i][len - 1];
		result[0] = lst[i][len - 2];
		cout << result;
	}
	cout << endl;
}

int main()
{
	Init();
	Print_PTA();
}


参考藏尾诗-PTA

删除字符串中的字串

又是需要输入空格的字符串，不能直接cin

一开始我的做法是利用cin.getline()函数得到了一个char类型的数组，然后自己写char数组的删除函数，相等判断函数

这明显就是重复造轮子的行为

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
const int defaultSize = 1000;
char s1[defaultSize], s2[defaultSize];
int len1 = 0, len2 = 0;

void Init()
{
	cin.getline(s1, defaultSize);
	cin.getline(s2, defaultSize);
	for (int i = 0; s1[i] != '\0'; i++)
	{
		len1++;
	}
	for (int i = 0; s2[i] != '\0'; i++)
	{
		len2++;
	}
}

bool Compare(char* str1, char* str2, int index)
{
	int it = 0;
	for (int i = index; str1[i] != '\0' && str2[it] != '\0'; i++)
	{
		if (str1[i] != str2[it])
		{
			return 0;
		}
		it++;
	}
	return 1;
}

void Remove(char* str, int len, int index)
{
	for (int i = index; str[i] != '\0'; i++)
	{
		str[i] = str[i + len];
	}

}

void Result()
{
	for (int i = 0; i < len1; i++)
	{
		if (s1[i] == s2[0])
		{
			if (Compare(s1, s2, i))
			{
				Remove(s1, len2, i);
				len1 -= len2;
				i = -1;			//每次重新回到开头找，即i=-1，这次for循环结束后i自增为0，即开头
			}
		}
	}
}

但是用cin.getline()只能得到char[]，没有string那么方便，还多加了很多时间用来造轮子和debug

虽然造轮子也是程序的浪漫，但是这无疑会消耗许多时间

这样的情况可以包含<string>头文件，里面有对getline()的重载，就可以直接输入带空格的字符串，并且还能利用string类型自带的函数，如erase(), find(), length()等可以节约许多时间

string的find()函数可以找一个指定字符，也可以找一个字符串，如果没找到返回值就是string::npos，通常是无符号int或无符号long的最大取值，这个值强制类型转换成int就是-1

1
2
3
4
5
6
7
8
9
10
11
void useStringtoSolve()
{
	string str1, str2;
	getline(cin, str1);
	getline(cin, str2);
	while (str1.find(str2) != string::npos)
	{
		str1.erase(str1.find(str2), str2.length());
	}
	cout << str1;
}


过了的完整代码如下，包括自己造轮子的写法在内，两种方法都能成功过这个题

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<string>

using namespace std;

const int defaultSize = 1000;

char s1[defaultSize], s2[defaultSize];
int len1 = 0, len2 = 0;

void Init()
{
	cin.getline(s1, defaultSize);
	cin.getline(s2, defaultSize);
	for (int i = 0; s1[i] != '\0'; i++)
	{
		len1++;
	}
	for (int i = 0; s2[i] != '\0'; i++)
	{
		len2++;
	}
}

void Print()
{
	for (int i = 0; i < len1; i++)
	{
		cout << s1[i];
	}
	cout << endl;
}

bool Compare(char* str1, char* str2, int index)
{
	int it = 0;
	for (int i = index; str1[i] != '\0' && str2[it] != '\0'; i++)
	{
		if (str1[i] != str2[it])
		{
			return 0;
		}
		it++;
	}
	return 1;
}

void Remove(char* str, int len, int index)
{
	for (int i = index; str[i] != '\0'; i++)
	{
		str[i] = str[i + len];
	}

}

void Result()
{
	for (int i = 0; i < len1; i++)
	{
		if (s1[i] == s2[0])
		{
			if (Compare(s1, s2, i))
			{
				Remove(s1, len2, i);
				len1 -= len2;
				i = -1;
			}
		}

	}
}

void useCharArrtoSolve()	//重复造轮子
{
	Init();
	Result();
	Print();
}

void useStringtoSolve()		//利用string解决
{
	string str1, str2;
	getline(cin, str1);
	getline(cin, str2);
	while (str1.find(str2) != string::npos)
	{
		str1.erase(str1.find(str2), str2.length());
	}
	cout << str1;
}

int main()
{
	//useCharArrtoSolve();
	useStringtoSolve();
}


参考字符串字串删除


需要注意的是，getline(cin, str);这个函数是直接从cin缓冲区中读的

也就是说，如果测试样例如图

想得到I love GPLT这个字符串，就得调用2次getline(cin, str);因为第一次调用得到的是空字符串

即使前面已经用cin获取了15 _这两个输入也不行，一定要调用两次才能得到所需字符串

cin的返回值

先放题

输入样例:

Hello World Here I Come

输出样例:

Come I Here World Hello


想到可以直接用cin函数跳过空格，然后空格留在缓冲区中，用一个getchar()可以把空格读出来

cin同时也会遇到回车结束，用一个getchar()可以把回车读出来，由此可以判断回车结束

但是这样正常结束的前提是像示例输入一样，一个单词几个空格，结尾必须是单词

如果结尾是空格，即测试点1，输入一个词，末尾有空格，就会一直卡在while循环的cin >> lst[i];步骤，不能正常结束，于是超时

同理，测试点3，只输入空格，也会一直卡在cin >> lst[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
void Init_char()		//失败了失败了失败了失败了失败了失败了失败了失败了
{
	char t = 't';
	int i = 0;
	while (t != 10)
	{
		cin >> lst[i];
		i++;
		N++;
		t = getchar();
	}
	for (i = N - 1; i > 0; i--)
	{
		cout << lst[i] << " ";
	}
	if (N > 0)
	{
		cout << lst[0] << endl;
	}
	else
	{
		return;
	}
}

如果把cin函数写在while循环判断条件里，就可以利用读到文件尾的返回值结束循环

OJ系统测试点都是读文件，所以可以利用这一特性来完成读空格和读回车的判断

如果把cin写在while的判断条件里，在Windows本地跑，需要手动输入ctrl+z模拟文件的EOF，才能正常结束

1
2
3
4
5
while (cin >> lst[i])
{
	i++;
	N++;
}


完整代码

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<iostream>

using namespace std;

const int defaultSize = 500010;

string lst[defaultSize];
int N = 0;

void Init()
{
	int i = 0;
	while (cin >> lst[i])
	{
		i++;
		N++;
	}
	for (i = N - 1; i > 0; i--)
	{
		cout << lst[i] << " ";
	}
	cout << lst[0] << endl;
}

void Init_char_fail()		//失败了失败了失败了失败了失败了失败了失败了失败了
{
	char t = 't';
	int i = 0;
	while (t != 10)
	{
		cin >> lst[i];
		i++;
		N++;
		t = getchar();
	}
	for (i = N - 1; i > 0; i--)
	{
		cout << lst[i] << " ";
	}
	if (N > 0)
	{
		cout << lst[0] << endl;
	}
	else
	{
		return;
	}
}

int main()
{
	Init();
	//Init_char_fail();		//失败了失败了失败了失败了失败了失败了失败了失败了
}


参考说反话-加强版

正则表达式

先放题

输入样例:

1
2
3
4
5
6
7
6
Hello ?
 Good to chat   with you
can   you speak Chinese?
Really?
Could you show me 5
What Is this prime? I,don 't know

输出样例:

1
2
3
4
5
6
7
8
9
10
11
12
Hello ?
AI: hello!
 Good to chat   with you
AI: good to chat with you
can   you speak Chinese?
AI: I can speak chinese!
Really?
AI: really!
Could you show me 5
AI: I could show you 5
What Is this prime? I,don 't know
AI: what Is this prime! you,don't know


此题我认为最难的部分在于替换这部分，空格的处理和大小写替换很容易实现

尝试写了判断单词分隔的问题，写了很久还是有问题

去网上找解决方案，查到了用正则表达式写的方法

正则表达式 regex 要包含<regex>头文件，只有在C++ 11以上版本才有这个，我拿dev-C++跑就报错，是因为C++版本不够

我唯一不会实现的功能就是Replace(str)函数，所以参考查找的代码看一下怎么替换单词：

1
2
3
4
5
6
s = regex_replace(s, regex(R"(\bcan you\b)"), "_I can");
s = regex_replace(s, regex(R"(\bcould you\b)"), "_I could");
s = regex_replace(s, regex(R"(\bI\b)"), "you");
s = regex_replace(s, regex(R"(\bme\b)"), "you");
s = regex_replace(s, regex(R"(\?)"), "!");
s = regex_replace(s, regex(R"(\b_I\b)"), "I");

用到了regex_replace(string str1, regex reg, string str2)函数，其返回值是一个修改好的字符串

修改的方式是：将str1中所有符合regex的内容替换为str2

中间regex类型的reg是正则表达式对象

注意，创建正则表达式对象的时候，要考虑转义字符，\\算作一个\

如下图代码所示

1
2
3
4
5
6
7
string str;
getline(cin, str);

regex reg("(\\bcan you\\b)");		//两个 \ 算作一个
str = regex_replace(str, reg, "_I can");
str = regex_replace(str, regex(R"(\b_I\b)"), "I");
cout << str;

输入can you do it ， 输出I can do it

但是每次要打两个\明显很麻烦，所以就有了示例代码的写法，用一个R表示里面的内容是纯字符串，即不再需要增加\来转义特殊字符

即

1
2
regex reg("(\\bcan you\\b)");
str = regex_replace(str, reg, "_I can");

和

1
str = regex_replace(str, regex(R"(\bcan you\b)"), "_I can");

功能完全相同

而中间用到的\b，就是用来判断单词边界的，例如正则表达式\bsome\b在字符串"some games"中能找到匹配，在字符串"something good"中却找不到

原码中还要注意处理大写I，即替换原句中me, I为you和替换原句can you, could you为I can, I could的顺序

源码替换can you的时候，先换的_I can，最后再把_I换成了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
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
77
78
79
#include<iostream>
#include<string>
#include<regex>

using namespace std;

const int defaultSize = 1010;

int N;

void Space(string& str)
{
	for (int i = 0; i < str.length(); i++)
	{
		if (i == 0 && str[i] == ' ' || str[i] == ' ' && str[i + 1] == ' ')
		{
			str.erase(i, 1);
			i--;
			continue;
		}

		if (str[i] == ' ' && (str[i + 1] >= 33 && str[i + 1] <= 47 || str[i + 1] >= 58 && str[i + 1] <= 64 || str[i + 1] >= 91 && str[i + 1] <= 96 || str[i + 1] >= 123 && str[i + 1] <= 126))
		{
			str.erase(i, 1);
			i--;
			continue;
		}
	}

	while (str[str.length() - 1] == ' ')
	{
		str.erase(str.length() - 1, 1);
	}
}

void Replace(string& str)
{
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] == '?')
		{
			str[i] = '!';
		}
		if (str[i] >= 'A' && str[i] <= 'Z' && str[i] != 'I')
		{
			str[i] += 'a' - 'A';
		}
	}
	str = regex_replace(str, regex(R"(\bcan you\b)"), "_I can");
	str = regex_replace(str, regex(R"(\bcould you\b)"), "_I could");
	str = regex_replace(str, regex(R"(\bI\b)"), "you");
	str = regex_replace(str, regex(R"(\bme\b)"), "you");
	str = regex_replace(str, regex(R"(\b_I\b)"), "I");
}

void Solve(string& str)
{
	Space(str);
	Replace(str);
}

void Result()
{
	cin >> N;
	string Question;
	getline(cin, Question);
	for (int i = 0; i < N; i++)
	{
		getline(cin, Question);
		cout << Question << endl;
		Solve(Question);
		cout << "AI: " << Question << endl;
	}
}

int main()
{
	Result();
}

其实也可以用正则表达式替换空格的，但是替换空格的函数我手动实现了，具体实现过程可以看参照的源码:

1
2
3
4
5
6
7
8
9
s = regex_replace(s, regex(R"(\s+)"), " ");		//把多个空格替换为一个空格，\s表示空格，+表示一次或多次
											//括号表示群组
if (s.front() == ' ') s.erase(s.begin());
if (s.back() == ' ') s.pop_back();
s = regex_replace(s, regex(R"( !)"), "!");		//把标点符号前的空格去除
s = regex_replace(s, regex(R"( ,)"), ",");
s = regex_replace(s, regex(R"( \.)"), ".");
s = regex_replace(s, regex(R"( \?)"), "?");
s = regex_replace(s, regex(R"( ')"), "'");


参考PTA 估值一亿的AI核心代码

参考C++正则表达式简单总结

利用map绑定string和int

先放题

处理这道题时碰到一个难以解决的问题：怎么让string类型的身份证号与int类型的申请时间绑定？

因为代码能力不足，所以想手动写一个哈希函数的想法失败了，于是上网找了相应解决方案

找到了C++的map容器，可以完美解决这个问题，又一次体会到了跳过重复造轮子过程的爽快感


map容器可以绑定两个一对一的数据，第一个数据为键，第二个数据为值

键不能重复，也不能修改，值可以随便修改

这就完美解决了身份证和时间的对应关系：身份证号独一无二，而申请时间可以随意修改

但是map容器存放顺序不是按输入顺序来的，而最后的输出需要按输入顺序，这个就很麻烦了

来看一下map容器的用法：

要包含<map>头文件

声明方法：map<string, int> IDtime;

map容器中存的键值对，本质都是 pair 类模板创建的 pair 对象，可以用{}简写，但是这里只记录map容器的用法

map容器实现了对[ ]运算符的重载，插入元素，查找元素，更新元素都可以用[ ]运算符实现

例如Mymap["WHITE ALBUM 2"] = 1; 如果Mymap里一开始没有键为"WHITE ALBUM 2"的元素，那就将这条元素插入容器中；如果有键为"WHITE ALBUM 2"的元素，那么就可以更新对应的值，可以利用这点很方便地进行插入和查找值

find()函数，参数带入键，如果不能找到键则返回Mymap.end()

插入的元素会按键的顺序从小到大存放在容器中，并不是按插入顺序存放的

用for循环迭代元素，先声明一个迭代器map<string,int>::iterator it;但是可以用auto来简写；结束条件为it != Mymap.end()，简写后的代码为for (auto it = Mymap.begin(); it != Mymap.end(); it++)

it的first元素为键，second元素为值

删除元素，调用erase()函数，可以指定键进行删除，也可以用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
int main()
{
	map<string, int> Mymap;

	//插入元素
	Mymap["WHITE ALBUM 2"] = 1;
	Mymap["サクラノ詩"] = 1;
	Mymap["STEINS;GATE"] = 2;
	Mymap["Ever17"] = 3;

	//查找指定键对应的值
	cout << Mymap["WHITE ALBUM 2"] << endl;

	//更新元素
	Mymap["WHITE ALBUM 2"] = 0;
	cout << Mymap["WHITE ALBUM 2"] << endl;

	//遍历元素
	for (auto it = Mymap.begin(); it != Mymap.end(); it++)
	{
		cout << it->first << " " << it->second << endl;
	}

	//删除元素
	Mymap.erase("Ever17");
	cout << endl;
	for (auto it = Mymap.begin(); it != Mymap.end(); it++)
	{
		cout << it->first << " " << it->second << endl;
	}
}


然后就是排序函数，sort()函数要包含<algorithm>头文件

排序函数要写比较函数，返回值为bool

调用如下：

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
const int defaultSize = 100;

struct info
{    
    int time;
    int idx;
};

bool cmp(info a, info b)
{
    if (a.time == b.time)
    {
        return a.idx < b.idx;
    }
    return a.time < b.time;
}

int main()
{
    info lst[defaultSize];
    for (int i = 0; i < defaultSize; i++)
    {
        lst[i].time = rand() % 100;
        lst[i].idx = i;
    }
    sort(lst, lst + defaultSize, cmp);
    for (int i = 0; i < defaultSize; i++)
    {
        cout << lst[i].time << " " << lst[i].idx << endl;
    }
}

输出为先按time从小到大排序，如果相同按idx由小到大排序


有了map和排序，就可以解决这个题了

首先是时间的换算，把输入的小时乘60再加分钟，可以得到一个时间，cmp()函数就用时间和输入顺序判断

注意输出时解决顺序问题，我的代码因为这个问题卡了4,5测试点，没有完全正确


参考map 详解 (C++)

参考【PTA-训练day23】L2-034 口罩发放

凯撒密码

很基础的问题了，但还是有要注意的地方

向左位移就是输入负值，但是这个负值可能非常大

所以正确的算法是先将位移值余26，如果得到小于0的数，这时的值就换成26 + N，这样就可以解决问题了


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

using namespace std;

string str;
long N;

void Init()
{
    getline(cin, str);
    cin >> N;

    N = N % 26;         //N<0且很大
    if (N < 0)
    {
        N = 26 + N;
    }

    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] >= 'A' && str[i] <= 'Z')
        {
            str[i] = (str[i] - 'A' + N) % 26 + 'A';
        }
        else if (str[i] >= 'a' && str[i] <= 'z')
        {
            str[i] = (str[i] - 'a' + N) % 26 + 'a';
        }
    }
    cout << str << endl;
}

int main()
{
    Init();
    return 0;
}

字符串总结

输入带字符的字符串：

用cin.getline()，得到一个char数组

包含<string>头文件，用getline(cin, string str)可以得到一个完整字符串，但注意getline()函数读相应位置的字符串就要对应调用多少次


一个汉字的UTF-8编码占2个字节，如果要显示单个汉字，就需要建立一个char数组，长度为3，下标为2的存'\0'，前面2个存对应的字节就好，输出就直接用cout，这样就可以显示一个单独的汉字


删除字符串字串，用string自带的函数find()和erase()，find函数没找到对应字串就会返回string::npos，用于循环结束；找到了就会返回对应位置的下标，可以传给erase()函数，并指定字串的长度


while (cin >> lst[i])问题，本地运行要手动ctrl+z


正则表达式，包含<regex>头文件，用\b判断单词分隔，用R指明纯字符串，不考虑\转换符

替换的时候用regex_replace(string str1, regex reg, string str2)函数


凯撒密码注意左移情况，先余26，若小于0再加26


map容器和排序函数

map多用[ ]的重载，不用考虑重复键情况，很好用

循环遍历可以简写为for (auto it = Mymap.begin(); it != Mymap.end(); it++)，这个auto很好用

排序函数手动实现bool cmp()函数，return期望的顺序，注意return的表达式不能带等号

考虑顺序问题时可以多一个idx变量，用于cmp()的比较




参考资料

PTA 实验7-3-8 统计字符出现次数

ACM小练习之字符串的处理

藏尾诗-PTA

字符串字串删除

说反话-加强版

PTA 估值一亿的AI核心代码

C++正则表达式简单总结

map 详解 (C++)

【PTA-训练day23】L2-034 口罩发放