首页 > 试题广场 >

万万没想到之聪明的编辑

[编程题]万万没想到之聪明的编辑
  • 热度指数：55771 时间限制：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
算法知识视频讲解
添加回答
Lunatic201904011812400头像 Lunatic201904011812400 
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)
kevin_Wang333头像 kevin_Wang333 
//我***了哭了。。。。。
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)
wyxwyxwyx头像 wyxwyxwyx 
#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)
Python
SuzumiyaG头像 SuzumiyaG
之前由于版本问题，代码在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)
Java
offerPlusPlus_头像 offerPlusPlus_
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)
TinyWind头像 TinyWind
自动机是一个非常方便的工具 

#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)
无心2019头像 无心2019 
#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)
zzd201906111340918头像 zzd201906111340918
// 使用有限自动机，一共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)
Remember201906102115596头像 Remember201906102115596 
#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)
Java
呃。。。头像 呃。。。 
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)
Java
牛客318434716号头像 牛客318434716号
从 i == 0开始，向前探测 [ i, i + 2 ] 查看是否需要删除，再向前探测[ i, i + 3 ] 查看是否需要删除。当两个窗口都正确后，i++。
剪枝：当剩余元素小于 i + 2 或 i + 3，以及 窗口第 i 个元素和第 i + 1 个元素不相同时，进行剪枝。 
public class Main{
     public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        for(int i = 0; i < n; i++){
            String s = input.next();
            String res = verify(new StringBuilder(s));
            System.out.println(res);
        }
    }
    
    public static String verify(StringBuilder s){
        if(s.length() <= 2){
            return s.toString();
        } 
        int i = 0;
        while(i < s.length()){
            if(i + 2 >= s.length()){
                break;
            } 
              // 窗口前2个值不等时，无需处理
            if(s.charAt(i) != s.charAt(i + 1)){
                i++;
                continue;
            }
            if(s.charAt(i + 1) == s.charAt(i + 2)){
                s.deleteCharAt(i + 2);
             // 删除第三个值后，进入下一次循环，重新判断窗口大小为3的情况是否满足
                continue;
            }
            if(i + 3 >= s.length()){
                break;
            }
            if(s.charAt(i + 2) == s.charAt(i + 3)){
                s.deleteCharAt(i + 3);
                continue;
            }
            i++;
        }
        return s.toString();
    }
}


编辑于 2021-03-15 08:59:05 回复(1)
Python
特种小狗头像 特种小狗 
"""
我可真笨啊，做了好久也坐了好久。。。
"""
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 回复(2)
Java
大大啊啊啊头像 大大啊啊啊 
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)
C/C++
胖十斤换网名的阿琛头像 胖十斤换网名的阿琛 
 #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
                                                    
                                                                                            
                                                回复(1)
                                                                                                                                            

                                        

                                


                                                            
                        

                        
                                        

                            

        


                    

                                    

                        

                            

                            

                                提交观点
                            

                        

                    

                            

            

    

          

            
问题信息

            

              

                                      C++工程师
                                      iOS工程师
                                      安卓工程师
                                      运维工程师
                                      字符串
                                      模拟
                                      算法工程师
                                      测试工程师
                                      PHP工程师
                                      字节跳动
                                      2019
                                      Java工程师
                                

                                  

                
                                                      

                          上传者：小小
                      

                                              

                                        难度：

                                

                                        255条回答
                      
                      65268浏览
                                

            

          

            




















                    

            

                        

  

    

      
      
      
    

    
热门推荐

  

  

    

      
    

  



            

                

            

          
                          

                

                  
通过挑战的用户

                                          查看代码
                                    

                

                  
                

              

                        

                          

                
相关试题

                

                  
                

              

            
                            

                        万万没想到之聪明的编辑
                

                





                
        

                                                                

        

    
    
    

    


            
    
    

        

            

                
            

            
扫一扫，把题目装进口袋

        

        

            
求职之前，先上牛客

            

                
                    

                        

                        

                            
                            
扫描二维码，进入QQ群

                        

                    

                
                
                    

                        

                        

                            
                            
扫描二维码，关注牛客公众号