标签搜索

目 录CONTENT

文章目录

字节跳动---万万没想到之聪明的编辑.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 17 阅读 / 2,576 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

万万没想到之聪明的编辑.md
date: 2021-08-22 12:11:42.512
updated: 2021-08-22 12:11:42.512
url: /2021/08/22/字节跳动---万万没想到之聪明的编辑md
categories:
tags:

字节跳动---万万没想到之聪明的编辑

@[toc]

一、题目描述

我叫王大锤,是一家出版社的编辑。我负责校对投稿来的英文稿件,这份工作非常烦人,因为每天都要去修正无数的拼写错误。但是,优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径:

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

我特喵是个天才!我在蓝翔学过挖掘机和程序设计,按照这个原理写了一个自动校对器,工作效率从此起飞。用不了多久,我就会出任CEO,当上董事长,迎娶白富美,走上人生巅峰,想想都有点小激动呢!
……
万万没想到,我被开除了,临走时老板对我说: “做人做事要兢兢业业、勤勤恳恳、本本分分,人要是行,干一行行一行。一行行行行行;要是不行,干一行不行一行,一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……

请听题:请实现大锤的自动校对程序

输入描述:

第一行包括一个数字N,表示本次用例包括多少个待校验的字符串。

后面跟随N行,每行为一个待校验的字符串。

输出描述:

N行,每行包括一个被修复后的字符串。

输入例子1:

2
helloo
wooooooow

二、分析

方法一:自动机

可以通过动态规划之KMP字符匹配算法来了解自动机的原理

对于本题也可以使用自动机的思想(以AB字符模拟):

在这里插入图片描述

  •  1.当第一次进入状态机的字母是A时,就处于0状态,继续判断下一个字符

  •  2.当第二次输入的字符不是A时,目前构成AX这种情况,不属于题意中的任意一个情况,状态不变,继续判断

  •  3.当第二次输入的字符还是A时,目前就构成AA这种情况,可能出现AAA,所以就进入1状态。

  •  4.当处于1状态时,第三次输入的字符如果不是A,目前构成AAB,可能会出现AABB型,所以需要判断,进入2状态

  •  5.当处于1状态时,第三次输入的字符如果是A,目前构成AAA,满足提议当中不能出现来连续3个同样的字符的情况,就需要删除一个,所以我们就忽略这个字符(就当没看见)

  •  6.如果当前处于2状态,第4次输入的字符如果还是B,那么就构成AABB型,属于题意中的情况,需要删除一个B,所以我们仍然忽略这个字符(就当没看见)

  •  7.如果当前处于2状态,第4次输入的字符如果不是B,那么就构成AABX型,不属于题意中的任意一个情况,状态变为0,继续判断

总结:0状态是用来处理不是AAA型或者AABB型的情况;1状态是用来解决AAA型的情况(忽略不加入结果集);2状态是用来解决AABB型的情况(忽略不加入结果集)

方法二:暴力求解

直接一趟遍历,把AAA的情况删除一个A,AABB的情况删除一个B,注意边界问题

三、代码

方法一:自动机模拟前后4个字符的情况

#include<iostream>
#include<string>
using namespace std;
 
int main() 
{
    int n;
    cin >> n;
 
    while (n--) 
    {
        int state = 0;//代表状态机🐔的3种状态,初始化为状态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,因为可能出现AAA的情况,否则是肯定出会出现,继续在状态0;
                    state = 1;    //进入状态1:AA形式
                else 
                	state = 0; //继续状态0:AB形式,即正常形式
                break;
            }
            
            case 1:
            {
                if (cur == last)
                    continue;//AAA,忽略即可,不加入结果集
                else
                    state = 2;//进入状态3:AAB形式,因为可能出现AABB的情况
                break;
            }
            
            case 2:
            {
                if (cur == last)
                    continue;//AABB,忽略即可,不加入结果集
                else
                    state = 0;//AABC,就是状态0,因为不可能出现AAA或AABB的情况
                break;
            }
            
            default:
                break;
            }

			//加入结果集
            ans = ans + cur;
            //更新上一个元素
            last = cur;
        }
        cout << ans << endl;
    }
    return 0;
}

方法二:暴力求解



#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    string s;
    while (n--)
    {
        cin >> s;
        //规则1:AAA的情况
        for(int i = 2; i < s.length(); i++) 
        {
        	//三个连续相等的字符
            if(s[i] == s[i-1] && s[i-1] == s[i-2]) 
            {
            	//删除
                s.erase(i, 1);
                i--;
                if(s.length() < 3)
                    break;
            }
        }
        //规则2:AABB的情况
        for(int i = 3; i < s.length(); i++) 
        {
            if(s[i] == s[i-1] && s[i-2] == s[i-3]) 
            {
            	//删除
                s.erase(i, 1);
                i--;
                if(s.length() < 4)
                    break;
            }
        }
        cout << s << endl;
    }
    return 0;
}

0

评论区