hihoCoder 1039:字符消除(字符串处理)

#1039 : 字符消除

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi最近在玩一个字符消除游戏。给定一个只包含大写字母"ABC"的字符串s,消除过程是如下进行的:

1)如果s包含长度超过1的由相同字母组成的子串,那么这些子串会被同时消除,余下的子串拼成新的字符串。例如"ABCCBCCCAA"中"CC","CCC"和"AA"会被同时消除,余下"AB"和"B"拼成新的字符串"ABB"。

2)上述消除会反复一轮一轮进行,直到新的字符串不包含相邻的相同字符为止。例如”ABCCBCCCAA”经过一轮消除得到"ABB",再经过一轮消除得到"A"

游戏中的每一关小Hi都会面对一个字符串s。在消除开始前小Hi有机会在s中任意位置(第一个字符之前、最后一个字符之后以及相邻两个字符之间)插入任意一个字符('A','B'或者'C'),得到字符串t。t经过一系列消除后,小Hi的得分是消除掉的字符的总数。

请帮助小Hi计算要如何插入字符,才能获得最高得分。

输入

输入第一行是一个整数T(1<=T<=100),代表测试数据的数量。

之后T行每行一个由'A''B''C'组成的字符串s,长度不超过100。

输出

对于每一行输入的字符串,输出小Hi最高能得到的分数。

提示

第一组数据:在"ABCBCCCAA"的第2个字符后插入'C'得到"ABCCBCCCAA",消除后得到"A",总共消除9个字符(包括插入的'C')。

第二组数据:"AAA"插入'A'得到"AAAA",消除后得到"",总共消除4个字符。

第三组数据:无论是插入字符后得到"AABC","ABBC"还是"ABCC"都最多消除2个字符。

样例输入

3
ABCBCCCAA
AAA
ABC

样例输出

9
4
2
题目链接:https://hihocoder.com/problemset/problem/1039
好吧,这题本身就是一道谷歌公司的面试题,虽然难度等级LV1,但。。。还是好难!!!
这道题思路是:在原字符串上的每个位置添加上A或B或C,然后去消除。因为字符串只由3种字母组成,并且插入的字符也只能是这三种字符的其中一个,那么可以考虑枚举这三个字符其中一个字符到字符串中任意一个位置。如果可以消除则不断消除,最后更新求得一个最大值。
这道题我不得不介绍一种函数-insert,在原有的字符串上插入一个字符!就是选定第i个位置,在第i个位置之后插入一个字符!函数写法为temp(字符串).insert(i,"某一字符");
下面给出AC代码:
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 string s;
 4 int del(string p)//每次执行,字符就会消除一次,直到不能消除为止
 5 {
 6     int len=p.size();
 7     int lent;
 8     if(len==0) return 0;//结束条件
 9     string t="";//删除后剩余的加到t上
10     int l=0;
11     p+="#";//加一个标志位
12     for(int i=1;i<=len;i++)
13     {
14         if(p[i]!=p[i-1])
15         {
16             if(l==i-1) t+=p[i-1];
17             l=i;
18         }
19     }
20     if((lent=t.size())==len) return 0;//结束条件
21     return len-lent+del(t);
22 }
23 int main()
24 {
25     int T;
26     while(scanf("%d",&T)!=EOF)
27     {
28         while(T--)
29         {
30             cin>>s;
31             int ans=0,t;
32             int len=s.size();
33             for(int i=0;i<=len;i++)
34             {
35                 string temp=s;
36                 temp.insert(i,"A");
37                 if((t=del(temp))>ans) ans=t;
38                 temp=s;
39                 temp.insert(i,"B");
40                 if((t=del(temp))>ans) ans=t;
41                 temp=s;
42                 temp.insert(i,"C");
43                 if((t=del(temp))>ans) ans=t;
44             }
45             cout<<ans<<endl;
46         }
47     }
48     return 0;
49 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(6) - 插入排序

1785
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

3856
来自专栏nnngu

算法02 七大排序之:直接选择排序和堆排序

上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

3587
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

18710
来自专栏ACM算法日常

一次看懂进制转换(阶乘是关键) - HDU 2031

对于二进制的转换,我们通常有这样的公式,例如对于一个二进制111001,转换为十进制xx:

1773
来自专栏算法修养

PAT 1012 数字分类 (20)

给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字: A1 = 能被5整除的数字中所有偶数的和; A2 = 将被5除后余1的数字按给出顺序进行交错...

2605
来自专栏ACM算法日常

基础算法|4 简单选择排序

我们之前已经了解了三种基础算法,分别为二分查找算法,冒泡排序算法,以及直接插入排序算法。俗话说得好,温故而知新,所以现在就让我们简单回顾一下之前的三种算法吧。...

1183
来自专栏Java3y

十道算法题[二]

前言 清明不小心就拖了两天没更了~~ 这是十道算法题的第二篇了~上一篇回顾:十道简单算法题 最近在回顾以前使用C写过的数据结构和算法的东西,发现自己的算法和数据...

3769
来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

1664
来自专栏软件开发 -- 分享 互助 成长

大整数相加和大整数相乘

大数问题是指操作数超过了计算机常用数据类型的存储范围,常常是用字符串来模仿整数相加和相乘运算来实现的,在模拟的过程中要注意考虑进位和边界条件。 1、大整数相加 ...

24710

扫码关注云+社区