首页 > 试题广场 > 万万没想到之聪明的编辑
[编程题]万万没想到之聪明的编辑
  • 热度指数:9291 时间限制: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
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 回复(19)
#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 回复(5)
//这题就暴力扫一遍就可以了,碰到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 回复(2)
// 使用有限自动机,一共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)
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 回复(11)

双指针。首先把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 回复(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)
 #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)
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)
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 <bits/stdc++.h>
using namespace std;
string check(string &str){
    string ans(1,str[0]);
    for(int i=1;i<str.size();i++){
        if(str[i]==str[i-1]){
            while(i+1<str.size()&&str[i]==str[i+1])
                i++;
            ans+=str[i-1];
            int j=ans.size()-1;
            if(j>=3&&ans[j-2]==ans[j-3])
                ans.pop_back();
        }
        else
            ans+=str[i];
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string t;
        cin>>t;
        cout<<check(t)<<endl;
    }
    return 0;
}

发表于 2019-11-10 16:32:35 回复(0)
#include <bits/stdc++.h>
using namespace std;

string F(string s){
    string t = "";
    char c='\0';
    int cnt=0,p=0;
    bool flag = false;
    for(int i=0;s[i];i++){
        if(c==s[i])
            cnt++;
        else{
            flag = !flag && cnt>=2;
            c = s[i];
            cnt = 1;
        }
        if(cnt<3 && !(flag && cnt==2))
            t += s[i];
    }
    return t;
}

int main(){
    int n;
    string s;
    cin>>n;
    while(n--){
        cin>>s;
        int l = s.length();
        cout<<F(s)<<endl;
    }
    return 0;
}

发表于 2019-09-30 08:52:24 回复(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 回复(0)
#include<iostream>
#include<string>
using namespace std;

int main(){
    int n;
    cin>>n;
    while(n --){
        string s;
        cin>>s;
        for(int i = 0;i <= s.length()-3;i ++){//只需要特判后面三个字符即可
            if(s[i] == s[i+1]){
                char flag = s[i];
                if(s[i + 1] == s[i+2]){
                    s.erase(i+2,1);
                    i -=1;
                }else if(s[i+1] != s[i+2] && s[i+2] == s[i+3]){
                    s.erase(i+3,1);
                    i-=1;
                }
            }
            
        }
        cout<<s<<endl;
    }
    
    return 0;
}
发表于 2019-07-10 19:44:49 回复(0)
C++ Solution with stack
#include <bits/stdc++.h>
using namespace std;
int main() {
    
    string line;
    int n;
    cin >> n;
    
    for(int i = 0; i < n; ++i) {
        stack<pair<char, int>> dict;
        cin >> line;
        for(size_t i = 0; i < line.size(); ++i) {
            if(dict.empty()) {
                dict.push({line[i], 1});
            } else {                
                //last char same with line[i]
                if(dict.top().first == line[i]) {
                    auto tmp = dict.top();
                    dict.pop();
                    
                    //AABB now
                    if(dict.size() != 0 && dict.top().second == 2)
                        dict.push(tmp);
                    else {
                        ++tmp.second;
                        dict.push(tmp);
                    }
                }
                else {
                    dict.push({line[i], 1});
                }    
                
                if(dict.top().second >= 3)
                    --dict.top().second;
            }
        }
        
        line = "";
        while(!dict.empty()) {
            auto tmp = dict.top();
            //cout << tmp.first << ' ' << tmp.second << endl;
            dict.pop();
            line += string(tmp.second, tmp.first);
        }
        reverse(line.begin(), line.end());
        cout << line << endl;
    }
}


发表于 2019-05-15 14:07:35 回复(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)
#include<iostream>
#include<string>
using namespace std;

int main(){
    int T;
    cin>>T;
    string s;
    while(T--){
        cin>>s;
        int k=0;
        for (int i=0;s[i];i++){
            s[k++]=s[i];
            if((k>=3)&&(s[k-1]==s[k-2])&&(s[k-2]==s[k-3])) k--;
            if((k>=4)&&(s[k-1]==s[k-2])&&(s[k-3]==s[k-4])) k--;
        }
        s[k]='\0';
        cout<<s<<endl;
    }
    return 0;
}

这什么意思?有哪里不一样嘛..  

发表于 2019-05-14 10:07:09 回复(4)
// 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)