这篇一早写好,原打算等竞赛结束再贴。可昨天发现网上已到处都有讨论及解答,就不再等了。
前些日子玩的一道题,虽然解题失败,但还是觉得值得记上一笔。题是这样的
给定一个字符串,仅由a,b,c 3种小写字母组成。当出现连续两个不同的字母时,你可以用另外一个字母替换它,如
- 有ab或ba连续出现,你把它们替换为字母c;
- 有ac或ca连续出现时,你可以把它们替换为字母b;
- 有bc或cb 连续出现时,你可以把它们替换为字母a。
你可以不断反复按照这个规则进行替换,你的目标是使得最终结果所得到的字符串尽可能短,求最终结果的最短长度。
输入:字符串。长度不超过200,仅由abc三种小写字母组成。
输出:按照上述规则不断消除替换,所得到的字符串最短的长度。
例如:
输入cab,输出2。因为我们可以把它变为bb或者变为cc。
输入bcab,输出1。尽管我们可以把它变为aab -> ac -> b,也可以把它变为bbb,但因为前者长度更短,所以输出1。
我对纯粹的数学公式推导还是很怕的。年纪越大,越偏文了?但这道题比起公式推导,推理的味道更浓些。
失败的原因是超时。似乎应该先读题,分析及做好准备后,再去答题。我直接点了进去,在倒计时的恫吓下,两个小时里啥都没干成...
挑战失败后,反倒静下心来。最先找到的规律就是重复的字母可以化简,比如三个a和一个a是等价的,4个b和2个b也是等价的。于是直接开写实现这个化简逻辑的代码。M大人也被我拖下水,途中参战。不愧是M大人,思路很直接:“每次消除时都能保证最短即可!”先找感觉再找理论支撑是M大人的风格。结果证明这个思路也是对的!一发命中也是M大人的风格!
我这时却陷入了困境——即便整理好重复的字符,依然a啊b啊c的团团混杂,看不出个所以然。在我打算放弃,M大人的一句话点亮了我的解题道路——虽然她自己不大在意——“c其实等价于ab!”。是的,如果c等价于ab,那么把c用ab(或ba)替换掉后,字符串就只剩下ab了,就又可以整理重复的字符了!哇哈哈!到这里才发现,原来我的思路就只是“整理”!”
这回学乖了,不写代码了,先观察分析——总是忘记这条多年来学到宝贵经验。我发现如果相同的奇数个字符无论多少个都会产生同样结果,偶数也同样。这样可以进一步化简,所有重复的奇数字符都算作一个,所有偶数的都算作两个。字符串最终化简成axbxax... x可能是1或2。到这里规律很容易找到:
c替换成ab;统计ab的个数;当a和b的个数都是偶数时,结果是两个;否则是一个。
M大人最终的逻辑则复杂些:
遍历字符串;尝试消除字符;不能消除则继续;如能消除,用再前一位和再后一位字符评价是否能保证最短(=即不同),能则消,否则继续;一旦有消除发生,重新遍历消除后的新字符串;遍历结束时检查是否存在可以消除但却没通过评价的情况,如果有则消除,重新遍历。
上面的逻辑再加上,如果该字符串全部字符相同——比如都是a——这样的特殊情况就全活了!
这里的论证不是那么严谨,但是结果我觉得是相当的...理想。
代码如下:
public class EraseChar {
private static Character[] chars = { 'a', 'b', 'c' };
public static void main(String args[]) {
Set<String> strings = new HashSet<>();
// start === 测试数据。
for (int i = 0; i < 100000; i++) {
fillRandom(strings);
}
strings.add("a");
strings.add("b");
strings.add("c");
strings.add("ab");
strings.add("abc");
strings.add("aa");
strings.add("aaa");
strings.add("aaaa");
strings.add("cacccc");
// end === 测试数据。
for (String s : strings) {
int min1 = gg(s);
int min2 = mm(s);
System.out.println("min1=" + min1 + ", min2=" + min2 + " {" + s + "}");
if (min1 != min2) {
throw new RuntimeException("Noooooooo!");
}
}
}
/**
* c替换成ab;统计ab的个数;当a和b的个数都是偶数时,结果是两个;否则是一个。
* @param s
* @return
*/
public static int gg(String s) {
char[] chars = s.toCharArray();
int length = chars.length;
if (isAllSame(chars)) {
return length;
}
int countA = 0;
int countB = 0;
for (char c : chars) {
switch (c) {
case 'c':
countA++;
countB++;
break;
case 'a':
countA++;
break;
case 'b':
countB++;
break;
}
}
if (countA % 2 == 0 && countB % 2 == 0) {
return 2;
}
return 1;
}
public static int mm(String s) {
char[] chars = s.toCharArray();
int length = chars.length;
if (isAllSame(chars)) {
return length;
}
LinkedList<Character> list = new LinkedList<>();
for (char c : chars) {
list.add(c);
}
return getMimi(list);
}
/**
* <ol>
* <li>尝试消除字符;
* <li>如不能消除则继续;
* <li>如能消除,用再前一位和再后一位字符评价是否能保证最短(=即不同),能则消,否则继续;
* <li>一旦有消除发生,重新遍历消除后的新字符串;
* <li>遍历结束时检查是否存在可以消除但却没通过评价的情况,如果有则消除,重新遍历。
* </ol>
* @param list
* @return
*/
public static Integer getMimi(List<Character> list) {
int size = list.size();
if (size == 1) {
return 1;
}
if (size == 2) {
return list.get(0).equals(list.get(1)) ? 2 : 1;
}
Integer position = null;
for (int i = 0, l = list.size() - 1; i < l; i++) {
Character first = list.get(i);
Character second = getElement(list, i + 1);
Character test = test(first, second);
if (test == null) {
continue;
}
Set<Character> comps = new HashSet<>();
Character prev = getElement(list, i - 1);
if (prev != null) {
comps.add(prev);
}
Character next = getElement(list, i + 2);
if (next != null) {
comps.add(next);
}
comps.remove(test);
if (comps.isEmpty()) {
position = (position == null) ? i : position;
continue;
}
replace(list, i, test);
return getMimi(list);
}
if (position == null) {
return list.size();
}
Character first = list.get(position);
Character second = getElement(list, position + 1);
Character test = test(first, second);
replace(list, position, test);
return getMimi(list);
}
private static boolean isAllSame(char[] chars) {
Character temp = null;
for (char c : chars) {
if (temp == null) {
temp = c;
continue;
}
if (!temp.equals(c)) {
return false;
}
}
return true;
}
private static Character test(char c1, char c2) {
return (c1 == c2) ? null : minus(c1, c2);
}
private static void replace(List<Character> list, int i, char c) {
list.remove(i);
list.remove(i);
list.add(c);
}
private static Character getElement(List<Character> list, int i) {
return (i >= list.size() || i < 0) ? null : list.get(i);
}
private static char minus(char c1, char c2) {
for (char c : chars) {
if (c != c1 && c != c2) {
return c;
}
}
throw new RuntimeException("wrong char!");
}
private static void fillRandom(Set<String> strings) {
Random r = new Random();
int size = r.nextInt(200);
StringBuilder sb = new StringBuilder(size);
for (int i = 0; i < size; i++) {
sb.append(chars[r.nextInt(3)]);
}
String s = sb.toString();
if (strings.contains(s)) {
fillRandom(strings);
}
strings.add(s);
}
}
分享到:
相关推荐
acm习题,字符串处理 ,必做题解析,题目经典,含有解析
matlab简单代码|Matlab代码实例:如何在 MATLAB 中删除字符串中的空格?.docx文档,中文教程。
1.去除字符串头部和尾部所包含的空格、制表符、换页符(全角和半角), 2.消除开头的制表符 3.消除结尾的制表符 4.去空格方法 5.读取文本后又转成文本
题目意思是给一个字符串aabbbassa,消除掉超过两次连续的字母,直到不能消除。 package 快手笔试; import java.util.Scanner; import java.util.Stack; public class Solution1 { public static void main(String...
字符串方法(修剪) js programm消除字符串开头和结尾的空格
s.strip('0') #消除字符串s左右两边的特殊字符(如'0'),字符串中间的'0'不会删除 例如: >>>s = '000hello00world000' >>>s.strip('0') 'hello00world' s.strip('12')等价于s.strip('21') 例如: >
字符串 难度中等5626收藏分享切换为英文接收动态反馈 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度...
KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高
此函数可用于从字符串元胞数组中消除重复的字符串元胞。
字符串替换(C语言 + C#) 内有书中方法,由于华为要求严格,为了消除PClint。
C#去掉特定字符(使用ASC码),本方法可以直接调用。
判断一个字符串是否为回文,即顺读和倒读都一样。
可以通过根据移位的T函数的某些双倍比率重写字符串方程来消除这些差异,然后这些比率满足更复杂的方程,这些方程等效于M. Jimbo和H. Sakai(q- PVI方程式)。 在q变形(“ 5d”)矩阵模型中,它们看起来要简单得多...
在 C++ 中,`substr()` 函数并不直接用于去除字符串的前后空格。可以结合其他函数和方法来实现消除前后空格的操作。一种详细解决方法。在 C++ 中,`substr()` 函数并不直接用于去除字符串的前后空格。可以结合其他...
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。...最后还需判断可不可以是奇数长度回文串,如果消除字符的个数和原字符串长度
使用股票代码从内容字符串中提取公司名称和股票代码。 更新-版本1.0.0 此gem已更新,以消除对open-calais gem的依赖,并支持新的增强的Open Calais API。 要求 必须有一个OpenCalais帐户才能使用此gem。 创建您的...
JSCrush算法消除了类似于zip算法的重复子字符串。 处理字符串以将普通的json字符换成不会在URL中转义的json字符。 可以用于压缩任何类型的字符串,但针对uri编码的JSON进行了优化。 在大多数情况下,算法速度是...
下面小编就为大家带来一篇JS 清除字符串数组中,重复元素的实现方法。小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
对应于AdS 5×S 5中最小表面的保形量规是奇异的,我们表明与保形因子差异相关的IR异常消除了先前报道的差异,具有精确的场理论结果。 我们还仔细检查保形异常消除并通过直接评估所有波动模式的相移来重新计算波动...
从haml模板中提取可能要翻译的字符串以进行I18n翻译。 替换文本,创建yaml文件,做所有您认为宏可以解决的事情,但最终并没有真正节省那么多时间。 自动消除这种痛苦。 一遍又一遍地使用它 它不翻译已翻译的键...