首页 > 试题广场 >

万万没想到之聪明的编辑

[编程题]万万没想到之聪明的编辑
  • 热度指数:54791 时间限制: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
示例2

输入

1
nowcoder

输出

nowcoder
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 回复(303)
//我***了哭了。。。。。
import java.util.*;
public class Main { 
public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            ArrayList<String> list = new ArrayList<>();

            int n = scan.nextInt();
            for(int j = 0 ;j < n;j++) {
                char[] chars = scan.next().toCharArray();
                String str = changeStr(chars);
                list.add(str);
            }
            for(int l = 0; l < list.size();l++) {
                System.out.println(list.get(l));
            }
        }
    }
    public static String changeStr(char[] chars) {
        ArrayList<Character> arraylist = new ArrayList<>();
        String str = "";
        for(int k = 0; k < chars.length;k++) {
            arraylist.add(chars[k]);
        }
        int i = 0;
        while( i < arraylist.size() - 2) {
            if ((arraylist.get(i) == arraylist.get(i + 1)) && (arraylist.get(i + 1) == arraylist.get(i + 2))) {
                arraylist.remove(i + 2);
                //System.out.println(arraylist.toString());
            } else {
                i++;
            }
        }
        int j = 0;
        while( j < arraylist.size() - 3 ) {
            if((arraylist.get(j) == arraylist.get(j + 1))&&  (arraylist.get(j + 2) == arraylist.get(j + 3))) {
                arraylist.remove(j+3);
            } else {
                j++;
            }
        }
        for(int k = 0; k < arraylist.size();k++) {
            str = str + arraylist.get(k);
        }
        return str;
    }
}

发表于 2020-08-11 00:18:59 回复(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 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 回复(1)
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)
之前由于版本问题,代码在python2运行不了,在python3里正常运行。
def main():
    n = input()
    if n == 0&nbs***bsp;n == None:
        return None
    for i in range(int(n)):
        s=input()
        j=1
        while(j<=len(s)-1):
            if j > 2:
                if (s[j]==s[j-1]==s[j-2]&nbs***bsp;(s[j]==s[j-1] and s[j-2]==s[j-3])):
                    s=s[:j]+s[j+1:]
                else:
                    j = j + 1
            elif (j > 1 and s[j]==s[j-1]==s[j-2]):
                    s=s[:j]+s[j+1:]
            else:
                j = j + 1
        print(s)
if __name__ == '__main__':
    main()


编辑于 2020-03-02 17:01:28 回复(2)
//最常规做法,复杂度O(n)
#include <iostream>
#include <string>
using namespace std;
void process(string &a){
    a+='0';
    int i=0;
    while(a[i]!='\0'){
        int count=1;
        int j;
        for(j=i+1;j<i+3 && a[j]!='\0';j++){
            if(a[j]==a[i]) count++;
            else break;
        }
        if(count==3){
            a.erase(i,1);
            i--;
        }
        else if(count==2){
            if(a[i+2]==a[i+3] && a[i+1]!='\0' && a[i+2]!='\0'){
                a.erase(i+2,1);
                i--;
            }           
        }
        i++;
    }
    a.erase(a.size()-1,1);
}
int main(){
    int n;
    cin>>n;
    string a;
    for(int i=0;i<n;i++){
        cin>>a;
        process(a);
        cout<<a<<endl;       
    }
}
发表于 2020-01-14 11:04:28 回复(0)
import sys
input = []
for line in sys.stdin:
    input.append(line.strip().split())
def correcter(s):
    i = 0
    while True:
        if i >= len(s): break
        flag = False
        if len(s) - i >= 3:
            if s[i] == s[i+1] and s[i] == s[i+2]:
                flag = True
                s = s[0:i+1] + s[i+2:]
        if len(s) - i >= 4:
            if s[i] == s[i+1] and s[i+2] == s[i+3] and s[i] != s[i+2]:
                flag = True
                s = s[0:i+2] + s[i+3:]
        if not flag: i += 1
    return s
for s in input[1:]:
    print(correcter(s[0]))
来尝尝咸淡
发表于 2019-09-21 22:02:45 回复(0)
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s=new Scanner(System.in);
        int num=s.nextInt();
        String[] inputStr=new String[num];
        for(int i=0;i<num;i++) {
            inputStr[i]=s.next();
        }
        for(int j=0;j<inputStr.length;j++) {
            String str=inputStr[j];
            for(int k=2;k<str.length();k++) {
                char ch=str.charAt(k);
                boolean tempFlag=true;
                boolean tempFlag2=false;
                for(int m=k-2;m<k;m++) {
                    char ch2=str.charAt(m);
                    if(ch!=ch2) {
                        tempFlag=false;
                    }
                }
                if(tempFlag==true) {
                    str=str.substring(0,k)+str.substring(k+1);
                    k--;
                }
                if(k>2) {
                    char ch3=str.charAt(k-3);
                    char ch4=str.charAt(k-2);
                    char ch5=str.charAt(k-1);
                    if(ch3==ch4&&ch4!=ch5&&ch==ch5) {
                        tempFlag2=true;
                    }
                    if(tempFlag2==true) {
                        str=str.substring(0,k-1)+str.substring(k);
                        k--;
                    }
                }
            }
            System.out.println(str);
        }
    }

}

发表于 2019-08-16 15:08:53 回复(1)
自动机是一个非常方便的工具

#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 回复(69)
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 回复(28)
#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 回复(28)
// helloo --> hello     // wooooooow --> woow     static String str1 = "helloo";     static String str2 = "wooooooow";     // 待校验的字符数(可连续相同的字符数)     static int checkNum = 2;     // 标志是否要开启校验     static boolean flag = false;     public static void main(String[] args) {         String[] array = str1.split("");         List<String> list = new ArrayList<>();         for (int i = 0; i < array.length; i++) {             // 从这个里面取一个就往list里面放一个             String c = array[i];             if (flag) {                 if (!contains(list, c, i)) {                     // 如果还能放就放                     list.add(c);                 }             } else {                 list.add(c);                 flag = contains(list, c, i);             }         }         StringBuffer sb = new StringBuffer();         for (String c : list) {             sb.append(c);         }         System.out.println(sb.toString());     }     /**      * 校验上一个字符是否和这个字符相同,相同返回true,不相同返回false      * 还可以用来判断list中是否已经存在两个连续的相同的数,如果存在返回true,不存在返回false      * @param list      * @param string      * @param index      * @return      */     public static boolean contains(List<String> list, String string, int index) {         if (index == 0) {             return false;         }         String str;         if (index > list.size() - 1) {             str = list.get(list.size() - 1);         } else {             str = list.get(index - 1);         }         // 说明这个字符与上一个字符相等,并且已经有两个连续的字符出现,返回true         if (str.equals(string) && check(list,checkNum)) {             return true;         }         return false;     }          public static boolean check(List<String> list,int num) {         int count = 1;         for (int i = 0;i < list.size();i++) {             String pre = list.get(i);             if (i == list.size() - 1) {                 return false;             }             String current = list.get(i+1);             if (pre.equals(current)) {                 count++;                 if (count == num) {                     // 说明相同的数已经满了                     return true;                             }         }         return false;     } 
编辑于 2019-07-03 22:03:20 回复(0)
//这题就暴力扫一遍就可以了,碰到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 回复(13)
// 使用有限自动机,一共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)

双指针。首先把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 回复(2)
#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 回复(3)
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 回复(1)
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)