首页 > 试题广场 > 万万没想到之聪明的编辑
[编程题]万万没想到之聪明的编辑
  • 热度指数:22217 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
我叫王大锤,是一家出版社的编辑。我负责校对投稿来的英文稿件,这份工作非常烦人,因为每天都要去修正无数的拼写错误。但是,优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径:

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

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

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

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

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


输出描述:
N行,每行包括一个被修复后的字符串。
示例1

输入

2
helloo
wooooooow

输出

hello
woow
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int line = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < line; i++) {
            System.out.println(scanner.nextLine().replaceAll("(.)\\1+","$1$1").replaceAll("(.)\\1(.)\\2","$1$1$2"));
        }
    }
}

😛😛

编辑于 2019-08-22 10:59:47 回复(33)
自动机是一个非常方便的工具

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


编辑于 2019-08-16 14:47:08 回复(8)
#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int n;
    cin>>n;
    string s;
    while(n--)
    {
        cin>>s;
        int j=0;
        for(int i=0;i<s.size();i++)
        {
            s[j++]=s[i];   //j还没用
            if(j>=3&&s[j-1]==s[j-2]&&s[j-2]==s[j-3]) 
                j--;
            if(j>=4&&s[j-1]==s[j-2]&&s[j-3]==s[j-4]) 
                j--;
        }
        s.erase(s.begin()+j,s.end());
        cout<<s<<endl;
    }
}

发表于 2019-07-19 21:43:49 回复(9)
n = int(input())
while n > 0:
    s = input()
    res = []
    for e in s:
        if len(res) < 2:
            res.append(e)
            continue
        if len(res) >= 2:
            if e == res[-1] and e == res[-2]:
                continue
        if len(res) >= 3:
            if e == res[-1] and res[-2] == res[-3]:
                continue
        res.append(e)
    print("".join(res))
    n -= 1
发表于 2019-05-28 20:41:10 回复(22)
//这题就暴力扫一遍就可以了,碰到3个连续的或者AABB删掉那个字符即可。。。
//当时没做出来。。。菜是原罪!
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = Integer.parseInt(sc.nextLine());
            for(int i = 0; i < n; i++){
                StringBuilder sb = new StringBuilder(sc.nextLine());
                for(int j = 2; j < sb.length(); j++){
                    if(sb.charAt(j) == sb.charAt(j - 1) 
                       && sb.charAt(j - 1) == sb.charAt(j - 2)){
                        sb.deleteCharAt(j);
                        j--;
                    }
                    else if(isPattern(sb, j - 3, j)){
                        sb.deleteCharAt(j);
                        j--;
                    }
                }
                System.out.println(sb.toString());
            }
        }
        sc.close();
    }
    public static boolean isPattern(StringBuilder sb, int i, int j){
        if(i < 0) return false;
        return sb.charAt(i) == sb.charAt(i + 1) &&
                sb.charAt(j - 1) == sb.charAt(j);
    }
}

发表于 2019-07-03 16:53:26 回复(7)
// 使用有限自动机,一共5个状态
// 流输入,流输出,时间复杂度O(n),空间复杂度O(1)
#include <iostream>

using namespace std;
int main()
{
    int n;
    cin >> n;
    while (n--) {
        int state = 0;
        char last = '\0';
        char x;
        while (cin >> x) {
            switch (state) {
                case 0:
                    if (x == last)
                        state = 1;
                    break;
                case 1:
                    if (x == last)
                        state = 2;
                    else
                        state = 3;
                    break;
                case 2:
                    if (x != last)
                        state = 3;
                    break;
                case 3:
                    if (x == last)
                        state = 4;
                    else
                        state = 0;
                    break;
                case 4:
                    if (x != last)
                        state = 0;
            }
            
            if (state != 2 && state != 4) {
                cout << x;
            }
            
            last = x;
        }
        
        cout << endl;
    }
}
发表于 2019-06-12 11:18:03 回复(3)
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    string s;
    while (n--)
    {
        cin >> s;
        //规则1
        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
        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;
}

发表于 2020-03-14 10:50:25 回复(0)

双指针。首先把str转换成list,两个指针j,k开始遍历,当符合aabb时,让k--,符合aaa时,k--


n = eval(input())

for i in range(n):

    s = list(input())

    k = 0

    for j in range(len(s)):

        s[k] = s[j]

        k += 1

        if k >= 3 and s[k-3] == s[k-2] and s[k-2]==s[k-1]: k -= 1

        if k >= 4 and s[k-4]==s[k-3] and s[k-1]==s[k-2]: k -= 1

    print(''.join(s[:k]))
发表于 2019-05-06 21:51:48 回复(1)
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        StringBuilder[] strs = new StringBuilder[n];
        for (int i=0;i<n;i++){
            strs[i] = new StringBuilder(in.next());
        }
        for (int i=0;i<n;i++){
            for (int j=0;j<=strs[i].length()-4;){
                if (strs[i].charAt(j) == strs[i].charAt(j+1)){         //AA
                    if (strs[i].charAt(j+1) == strs[i].charAt(j+2) ||
                            strs[i].charAt(j+2) == strs[i].charAt(j+3)){    //AAAX或者AABB
                        strs[i].deleteCharAt(j+2);
                        continue;
                    }
                }else{
                    if (strs[i].charAt(j+1) == strs[i].charAt(j+2) &&
                            strs[i].charAt(j+2) == strs[i].charAt(j+3)){      //XAAA
                        strs[i].deleteCharAt(j+2);
                        continue;
                    }
                }
                j++;
            }
        }
        for (int i=0;i<n;i++)
            System.out.println(strs[i].toString());
    }
}

发表于 2019-08-15 19:51:35 回复(0)
 #include<iostream>
#include<string>
using namespace std;

int n, i = 0;
void _move(string m[],int x,int num,int *len)
{
    while (num < *len)
    {
        m[x][num] = m[x][num + 1];
        num++;
    }
}
void Allcheck(string sss[],int x,int *len)
{
    i = 1;
    int count = 0;
    if (*len < 4)
    {
        if (sss[x][0] == sss[x][1] && sss[x][1] == sss[x][2])
        {
            sss[2] = '\0';
            *len--;
        }
        return;
    }
    while (i < *len - 1 - count)
    {
        if (i < *len - 1 && sss[x][i - 1] == sss[x][i] && sss[x][i] == sss[x][i + 1])
        {
            _move(sss, x, i + 1, len);
            count++;
        }
        else if (i < *len - 2 && sss[x][i - 1] == sss[x][i] && sss[x][i + 1] == sss[x][i + 2])
        {
            _move(sss, x, i + 2, len);
            count++;
        }
        else
            i++;
    }

}
void check(string s***r /> {
    int len,j = 0;
    for (j = 0; j < n; j++)
    {
        len = ss[j].size();
        if (len < 3)
            continue;
        else
        {
                     }
    }
}
int main()
{
    cin >> n;
    string *s = new string[n];
    i = 0;
    while (i < n && cin >> s[i++]);
    check(***r />     i = 0;
    while (i < n)
    {
        cout << s[i++] << endl;
    }
    return 0;
 }

发表于 2019-05-18 18:29:32 回复(0)
n = int(input())
verify_string = []
for i in range(n):
    s = input()
    string = []
    for i in s:
        if len(string)>=2 and i == string[-1] == string[-2]:
            continue
        elif len(string) >=3 and i == string[-1] and string[-2]==string[-3]:
            continue
        else:
            string.append(i)
    verify_string.append("".join(string))

for i in verify_string:
    print(i)

编辑于 2019-08-17 17:03:16 回复(0)
"""
我可真笨啊,做了好久也坐了好久。。。
"""
import sys                       #前两行是标准输入语句,做公司真题时候需要这么写的,不然过不去
for s in list(sys.stdin)[1:]:
    try:                       #这里的try好像没啥用,写上保险点
        res = []             #接下来就是常规思路了,搞一个列表然后把待检测字符串一个字符一个字符的喂进去
        for s0 in s.strip():
            if len(res) < 2:
                res.append(s0)
                continue
            if len(res) >= 2:
                if s0 == res[-1] and s0 == res[-2]:
                    continue
            if len(res) >= 3:
                if s0 == res[-1] and res[-2] == res[-3]:
                    continue
            res.append(s0)
        print("".join(res))
    except:
        pass

发表于 2019-07-13 09:14:56 回复(0)
public class Main1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] strings = new String[N];
        for (int i = 0; i < N; i++) {
            strings[i] = sc.next();
        }
        Solution1 solution = new Solution1();
        for (String str : strings)
            System.out.println(solution.solve(str));
    }
}
class Solution1 {
    public String solve(String s) {
        if (s == null || s.length() <= 2) return s;
        for (int i = 0; i < s.length() - 3; i++) {
            if (s.charAt(i) == s.charAt(i + 1) && s.charAt(i + 2) == s.charAt(i + 3)) {//AABB
                s = delete(s, i + 2);
                i--;
            }
            else if(s.charAt(i) == s.charAt(i + 1) && s.charAt(i) == s.charAt(i + 2)){//AAA
                s = delete(s,i);
                i--;
            }
        }
        int n = s.length();
        if(s.charAt(n - 1) == s.charAt(n - 2) && s.charAt(n - 1) == s.charAt(n - 3))//可能结尾剩余3个AAA的情况
            s = delete(s,n-1);
        return s;
    }
    private String delete(String s, int i) {
        return s.substring(0, i) + s.substring(i + 1);
    }
}

发表于 2019-07-01 14:05:41 回复(0)
#include <stdio.h>
#include <stdlib.h>
#define MAX_LENGTH 1000
/************使用快指针和慢指针解决*******************/
int main()
{
    int num;  
    scanf("%d",&num);
    char **test=(char**)malloc(sizeof(char*)*num);
    for(int i=0;i<num;i++){
        test[i]=(char*)malloc(sizeof(char)*MAX_LENGTH);
        memset(test[i],0,sizeof(char)*MAX_LENGTH);
        scanf("%s",test[i]);
        char *fast=test[i];
        char *slow=(char*)malloc(sizeof(char)*MAX_LENGTH);
        memset(slow,0,sizeof(char)*MAX_LENGTH);
        int j_slow=0;
        for(int j=0;fast[j]!=0;j++){
            if(j>=2&&((slow[j_slow-2]==slow[j_slow-1])&&(slow[j_slow-1]==fast[j]))){//helllo->hello
                continue;
            }
            if(j>=3&&((slow[j_slow-3]==slow[j_slow-2])&&(slow[j_slow-1]==fast[j]))){//aabb->aab
                continue;
            }
            else{
                slow[j_slow++]=fast[j];
            }
        }
        for (int k=0;k<j_slow;k++){
            printf("%c",slow[k]);
        }
        printf("\n");
        free(slow);
    }
    return 0;
}


发表于 2020-06-29 21:54:05 回复(0)
看来字符串处理的题目正则才是王道!
string replace(string input, string regStr, string rep){
     regex reg(regStr);
     return regex_replace(input, reg, rep);
 }
 int main(){
     int n;
     cin>>n;
     while(n--){
         string input;
         cin >> input;
         cout << replace(replace(input, "(.)\\1+", "$1$1"), "(.)\\1(.)\\2", "$1$1$2") << endl;
     }
     return 0;
 } 

编辑于 2020-06-14 21:54:36 回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string motifyStr(string str)
{
	int last = 0;
	int i = 0;
	while (i < str.size())
	{
		while (str[i] != str[i + 1] && (i+1) < str.size())
		{
			i++;
		}
		last = i;
		if (str[last] == str[last + 1] && str[last] == str[last + 2] && (i+2) < str.size())
		{
			str.erase(last, 1);
		}
		else if (str[last] == str[last + 1] && str[last + 2] == str[last + 3] && (last + 3) < str.size())
		{
			str.erase(last + 2, 1);
		}
		else
			i++;
	}
	return str;
}
int main()
{
	int n;
	string temp;
	vector<string> res;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		string tmp= motifyStr(temp);
		res.push_back(tmp);
	}
	for (auto x : res)
		cout <<x<< endl;
	system("pause");
	return 0;
}

发表于 2020-06-10 16:40:47 回复(0)

常规解: 扫描一遍字符串

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string check(string& str)
{
    int times=1;//字符出现的次数
    bool isTwice=false;//BB情况下,之前是否有AA
    char c=str[0];//上一个字符
    for(int i=1;i<str.length();i++)
    {
        //记录状态
        if(str[i]==c) 
            times++;
        else 
        {
            if(times!=2)//上一个元素不是AA,则置为false
                isTwice=false;
            times=1;//重新计算
        }
        //该状态下是否要处理
        if(isTwice&&times==2||times==3)
        {
            str.erase(i,1);
            times--;
            i--;
        }
        if(times==2) isTwice=true;
        //更新上一个字符
        c=str[i];
    }
    return str;
}

int main()
{
    int N;
    cin>>N;
    vector<string> vec;
    for(int i=0;i<N;i++)
    {
        string str;
        cin>>str;
        str=check(str);
        vec.push_back(str);
    }
    for(auto e:vec)
        cout<<e<<endl;
}
  • 第一次做这种输入输出的题,记录一下
  • 有不妥的地方,给位可以给点建议
编辑于 2020-05-16 11:31:18 回复(0)
import re
def repair(s):
    # (.)\1 -> \1表示.匹配到的第一个字符
    res = re.sub(r'(.)\1\1+', repl=lambda x: x.groups(0)[0]*2, string=s) # 消除三个以上连续
    res = re.sub(r'(.)\1(.)\2', repl=lambda x: x.groups(0)[0]*2+x.groups(0)[1], string=res)
    return res

编辑于 2020-04-27 21:21:32 回复(0)
package main

import(
    "fmt"
)

const (
    XXXXAB = 0
    XXXXAA = 1
    XXXAAB = 2
    XXAABC = 3
)


func StrCheck(str string)string{
    //aabb
    var tmp []byte
	tmp = append(tmp,str[0])
	var flag int 
    
    for i := 1;i < len(str);i++{
        if tmp[len(tmp) - 1] == str[i]{
            if flag == XXXXAB || flag == XXAABC{//XXXXAB[B] || XXAABC[C]
                flag = 1
                tmp = append(tmp,str[i])
            } else if flag == XXXXAA || flag == XXXAAB{//XXXXAA[A] || XXXAAB[B]
                continue
            }
        } else {// [...a]b
            if flag == XXXXAB || flag == XXAABC{//XXXXAB[C]
                flag = 0
                tmp = append(tmp,str[i])
            } else if flag == XXXXAA{ //XXXXAA[B]
                flag = 2
                tmp = append(tmp,str[i])
            } else if flag == XXXAAB{
				flag = 3
				tmp = append(tmp,str[i])
			}
        }
    }
    return string(tmp)
}

func main(){
    var num int
    fmt.Scanf("%d\n",&num)
    res := make([]string,num)
    
    for i := 0;i < num;i++{
        var str string
        fmt.Scanf("%s\n",&str)
        res[i] = StrCheck(str)
    }
    for i,_ := range res{
        fmt.Println(res[i])
    }
}
来个Go的解题方法
发表于 2020-04-05 14:20:55 回复(0)
//超简单的思路,时空复杂度也比较低,只需设置维护一个flag(值有0 1 2),把字符一个一个拿出来就行了
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();    //消除遗留的Enter符
        for(int i = 1; i <= num; i++) {
            String s = sc.nextLine();
            if(s.length() <= 2) System.out.println(s);
            StringBuilder sb = new StringBuilder();
            int flag = 0;
            char[] cArr = s.toCharArray();
            if(cArr[0] == cArr[1]) flag = 2;
            sb.append(cArr[0]).append(cArr[1]);
            for(int j = 2; j < cArr.length; j++) {
                if(flag == 0) {
                    sb.append(cArr[j]);
                    if(sb.charAt(sb.length() - 1) == sb.charAt(sb.length() - 2)) flag = 2;
                } else {
                    if(cArr[j] != sb.charAt(sb.length() - 1)) {
                        sb.append(cArr[j]);
                        flag--;
                    }
                }
            }
            System.out.println(sb.toString());
        }
    }
}
编辑于 2020-03-05 15:07:29 回复(0)