算法刷题笔记|牛客网字节跳动2019真题聪明的编辑正则表达式字符串|字符串|正则表达式|c

文章目录

1. 题目描述

1.1. Title
1.2. Time Limit
1.3. Memory Limit
1.4. Problem Description
1.5. Input
1.6. Output
1.7. Sample Input
1.8. Sample Output
1.10. Source

2. 题解
3. 代码

1. 题目描述 1.1. Title
万万没想到之聪明的编辑
1.2. Time Limit
C/C++ 1秒，其他语言2秒
1.3. Memory Limit
C/C++ 32M，其他语言64M
1.4. Problem Description
我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：

三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！
万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……
请听题：请实现大锤的自动校对程序
1.5. Input
第一行包括一个数字N，表示本次用例包括多少个待校验的字符串。
后面跟随N行，每行为一个待校验的字符串。
1.6. Output
N行，每行包括一个被修复后的字符串。
1.7. Sample Input

2 helloo wooooooow

1.8. Sample Output

hello woow

1.10. Source
牛客网字节跳动2019 聪明的编辑
2. 题解使用正则表达式中的子模式匹配。regex("(.)\\1+")表示匹配任意字符两次以上，(.)代表匹配任意字符的一个子模式，\\1表示重复子模式1一遍，+表示匹配1到n次。
使用regex_replace可以把所有AAA替换成AA。

str = regex_replace(str, regex("(.)\\1+"), "$1$1", regex_constants::match_default);

同样也可以把所有AABB替换成AAB。

str = regex_replace(str, regex("(.)\\1(.)\\2"), "$1$1$2", regex_constants::match_default);

3. 代码

#include #include using namespace std; int main() { string str; // test case int n; cin >> n; // 对每个正则表达式 while (n--) { cin >> str; // 匹配aaa str = regex_replace(str, regex("(.)\\1+"), "$1$1", regex_constants::match_default); // 匹配aabb str = regex_replace(str, regex("(.)\\1(.)\\2"), "$1$1$2", regex_constants::match_default); cout << str << endl; } }

刚开始写了一个更复杂的版本，用regex_search找出所有匹配的子串并进行替换。
虽然regex_search本来可以一次找出所有的匹配串，但是这里要考虑替换的优先级，所以每替换一次需要重新搜索，也带来了重复的开销。

#include #include using namespace std; int main() { string str, buffer; size_t size; // test case int n; cin >> n; // 结束符号 sregex_iterator end; // 匹配集合 smatch m; // 匹配aabb 和 aaa string list[] = { "(([a-z])\\2\\2)", "(([a-z])\\2([a-z])\\3)" }; // 对每个正则表达式 while (n--) { cin >> str; for (int i = 0; i < 2; i++) { while (regex_search(str, m, regex(list[i]))) { buffer = m.str(0); size = buffer.size(); // 替换匹配项 str = str.replace(str.find(buffer), size, buffer.substr(0, size - 1)); } }cout << str << endl; } }

牛客网上还有一位用户的题解使用的是状态机，看着也很清晰。

#include #include using namespace std; int main() { //自动机 int n; cin >> n; while (n--) { int state = 0; //初始化为状态0 char cur; //当前字符 string str; //目标字符串cin >> str; char last = str[0]; //初始化为第一个字符string ans = ""; ans += str[0]; //初始化for (int i = 1; i < str.size(); ++i) {//开始 cur = str[i]; switch (state) { case 0: { if (cur == last)//如果是相等的，进入状态1，否则继续状态0； state = 1; //进入状态1：AA形式 else state = 0; //继续状态0：AB形式，即正常形式 break; } case 1: { if (cur == last) continue; //AAA,忽略即可 else state = 2; //进入状态3：AAB形式 break; } case 2: { if (cur == last) continue; //AABB，忽略即可 else state = 0; //AABC，就是状态0 break; } default: break; } ans = ans + cur; last = cur; } cout << ans << endl; } return 0; }

联系邮箱：curren_wong@163.com
CSDN：https://me.csdn.net/qq_41729780
知乎：https://zhuanlan.zhihu.com/c_1225417532351741952
公众号：复杂网络与机器学习
欢迎关注/转载，有问题欢迎通过邮箱交流。
【算法刷题笔记|牛客网字节跳动2019真题聪明的编辑正则表达式】