开发者社区> 橘子红了呐> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

算法:字符串消除问题的数学证明

简介:
+关注继续查看

问题:

给定一个字符串,仅由A、B、C3个字母组成。当出现连续两个不同的字母时,你可以用另外一个字母替换它,如有AB或BA连续出现,你把它们替换为字母C;有AC或CA连续出现时,你可以把它们替换为字母B;有BC或CB连续出现时,你可以把它们替换为字母A。可以不断反复按照这个规则进行替换,目标是使得最终结果所得到的字符串尽可能短,求最终结果的最短长度。

输入:字符串。长度不超过200,仅由ABC3个字母组成。 输出:按照上述规则不断消除替换,所得到的字符串最短的长度。

 

例如:

输入CAB,输出2。因为我们可以把它变为BB或者变为CC。

输入BCAB,输出1。我们可以把它变为AAB到AC到B,也可以把它变为BBB,但因为前者长度更短,所以输出1。

 

 

 

先给出几个概念

纯字符串:只含有一种字母的字符串称为纯字符串,例如AAA就是一个纯字符串

混字符串:含有至少两种字母的字符串称为混字符串,例如ABC就是一个混字符串

最优长度:字符串通过消除的最终结果的最短长度,称为该字符串的最优长度。上面的示例中,CAB的最优长度为2,BCAB的最优长度为1

最优串:字符串通过消除达到最优长度时的字符串称为最优串最优串可能不止一个。如CAB的最优串为BB和CC,而BCAB的最优串为B。最优串一定是纯字符串

统计向量:用(X,Y,Z)表示字符串的统计向量,其中X、Y、Z分别表示字符串中字母A、B、C的个数。上面的示例中,CAB的统计向量为(1,1,1),BCAB的统计向量为(1,2,1)

统计特征向量:用(X,Y,Z)表示字符串的统计特征向量,其中X、Y、Z分别表示字符串中字母A、B、C的个数的奇偶性,用“奇”、“偶”表示。CAB的统计特征向量为(奇,奇,奇),BCAB的统计特征向量为(奇,偶,奇)

 

 

 

再给出几个推论

推论1纯字符串最优长度就是纯字符串的长度。

很明显的,只有一个字母,没法消除,所以最优长度就是纯字符串的长度

 

推论2:在纯字符串前或后加另一个字母得到新的混字符串,则新混字符串最优长度为1

例如:BBBBBBBA。则消除的过程是,BBBBBBBA >> BBBBBBC >> BBBBBA >> BBBBC >> BBBA >> BBC >> BA >> C

其他的类似,不再赘述

 

推论3:若纯字符串的长度为偶数,则在前或后添加另一个字母得到新的混字符串,则新混字符串最优串为添加的字母;若纯字符串的长度为奇数,则新混字符串最优串为剩下的一个字母

假设纯字符串为BB,添加字母A,则新混字符串为BBA,BBA >> BC >> A

假设纯字符串为BBBB,添加字母A,则新混字符串为BBBBA,BBBBA >> BBA >> A

以此类推,推论3的前半部得证

假设纯字符串为B,添加字母A,则新混字符串为BA,BA >> C

假设纯字符串为BBB,添加字母A,则新混字符串为BBBA,BBBA >> BA >> C

以此类推,推论3的后半部得证

 

推论4混字符串最优长度不超过2(为1或2)

证明:

首先混字符串通过不停的消除,最终能得到一个纯字符串(因为若还有不同的字母,则必相邻,则还能继续消除)。

若该纯字符串的长度为1或2,则证明了该推论(不过,就算纯字符串长度为2,还没证明最优长度一定是2,可以肯定的是最优长度不超过2,即1或2都有可能)

若该纯字符串的长度大于2,不失一般性,假设该纯字符串的长度为K(K>2),该纯字符串都由字母B组成(字母A、C是一样的),该纯字符串是通过N(N≥1)步消除得到的

那么回退一步,第N-1步消除得到的混字符串为B……BACB……B,其中A前面有K1个B,C后面有K2个B,K1+K2=K-1。(也有可能是B……BCAB……B,和B……BACB……B是一致的,不再赘述了)

那么,根据K1和K2的取值不同,可以优化出不同的消除

K1是奇数,K2是奇数。利用推论3,可知B……BA >> C;CB……B >> A;B……BACB……B >> CA >> B,最优串是B,最优长度为1

K1是奇数,K2是偶数。利用推论3,可知B……BA >> C;CB……B >> C;B……BACB……B >> CC,则最优长度不超过2(因为还没法证明最优长度不会是1)

K1是偶数,K2是奇数。利用推论3,可知B……BA >> A;CB……B >> A;B……BACB……B >> AA,则最优长度不超过2(因为还没法证明最优长度不会是1)

K1是偶数,K2是偶数。利用推论3,可知B……BA >> A;CB……B >> C;B……BACB……B >> AC >> B,最优串是B,最优长度为1

综上所述,混字符串最优长度不超过2

 

推论5统计特征向量为(奇,奇,奇)或(偶,偶,偶)的混字符串最优长度为2;其余的混字符串最优长度为1

证明:

考察一下,每次消除,统计特征向量的变化过程

 

假设字符串的统计特征向量为(奇,奇,奇)

假设消除是AC(或CA) >> B,则A和C的个数减1,而B的个数增加1,则统计特征向量变为(偶,偶,偶)

假设消除是AB(或BA) >> C,则A和B的个数减1,而C的个数增加1,则统计特征向量变为(偶,偶,偶)

假设消除是BC(或CB) >> A,则B和C的个数减1,而A的个数增加1,则统计特征向量变为(偶,偶,偶)

综上所述,统计特征向量为(奇,奇,奇)的混字符串,经过1次消除后,统计特征向量变为(偶,偶,偶)

同理可证,统计特征向量为(偶,偶,偶)的混字符串,经过1次消除后,统计特征向量变为(奇,奇,奇)

由此可知,反复消除后,统计特征向量为(奇,奇,奇)的混字符串最优串统计特征向量是(偶,偶,偶)。(因为最优串纯字符串,只能有1种字符,所以最优串不可能是(奇,奇,奇))

同理可证,统计特征向量为(偶,偶,偶)的混字符串最优串统计特征向量也是(偶,偶,偶)。

因此,统计特征向量为(奇,奇,奇)或(偶,偶,偶)的混字符串最优串统计特征向量为(偶,偶,偶)

 

假设字符串的统计特征向量为(奇,偶,偶)

假设消除是AC(或CA) >> B,则A和C的个数减1,而B的个数增加1,则统计特征向量变为(偶,奇,奇)

假设消除是AB(或BA) >> C,则A和B的个数减1,而C的个数增加1,则统计特征向量变为(偶,奇,奇)

假设消除是BC(或CB) >> A,则B和C的个数减1,而A的个数增加1,则统计特征向量变为(偶,奇,奇)

综上所述,统计特征向量为(奇,偶,偶)的混字符串,经过1次消除后,统计特征向量变为(偶,奇,奇)

同理可证,统计特征向量为(偶,奇,奇)的混字符串,经过1次消除后,统计特征向量变为(奇,偶,偶)

由此可知,反复消除后,统计特征向量为(奇,偶,偶)的混字符串最优串统计特征向量是(奇,偶,偶)。(因为最优串纯字符串,只能有1种字符,所以最优串不可能是(偶,奇,奇))

同理可证,统计特征向量为(偶,奇,奇)的混字符串最优串统计特征向量也是(奇,偶,偶)。

因此,统计特征向量为(奇,偶,偶)或(偶,奇,奇)的混字符串最优串统计特征向量为(奇,偶,偶)

 

同理可证

统计特征向量为(偶,奇,偶)或(奇,偶,奇)的混字符串最优串统计特征向量为(偶,奇,偶)

统计特征向量为(偶,偶,奇)或(奇,奇,偶)的混字符串最优串统计特征向量为(偶,偶,奇)

 

由推论4可知,混字符串最优长度不超过2

如果,混字符串最优长度为1,则最优串是A,统计特征向量是(奇,偶,偶);是B,统计特征向量是(偶,奇,偶);是C,统计特征向量是(偶,偶,奇)

如果,混字符串最优长度为2,则最优串是AA或BB或CC,统计特征向量是(偶,偶,偶)

 

所以,统计特征向量为(奇,奇,奇)或(偶,偶,偶)的混字符串最优长度是2。

统计特征向量为(奇,偶,偶)或(偶,奇,奇)的混字符串最优长度为1,最优串是A

统计特征向量为(偶,奇,偶)或(奇,偶,奇)的混字符串最优长度为1,最优串是B

统计特征向量为(偶,偶,奇)或(奇,奇,偶)的混字符串最优长度为1,最优串是C

 

证明完毕

 

 

结论:

1、纯字符串最优串就是自身,最优长度就是自身的长度

2、统计特征向量为(奇,奇,奇)或(偶,偶,偶)的混字符串最优长度为2

3、其余的混字符串最优长度是1,其中统计特征向量为(奇,偶,偶)或(偶,奇,奇)的混字符串最优串是A;统计特征向量为(偶,奇,偶)或(奇,偶,奇)的混字符串最优串是B;统计特征向量为(偶,偶,奇)或(奇,奇,偶)的混字符串最优串是C


    本文转自万仓一黍博客园博客,原文链接:http://www.cnblogs.com/grenet/p/3300591.html,如需转载请自行联系原作者



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
②MySQL的函数——聚合函数、数学函数、字符串函数、日期函数
MySQL的函数——聚合函数、数学函数、字符串函数、日期函数
15 0
python数据类型入门(一)之字符串、布尔类型和日期时间
python数据类型入门(一)之字符串、布尔类型和日期时间
37 0
诡异的字符串问题。。。
说问题前,我先跟各位读者聊一下字符串这个话题,谈起字符串也就离不开数据结构
25 0
字符串匹配之 BM 算法
字符串匹配是计算机科学领域中最古老、研究最广泛的问题之一,层出不穷的前辈们也总结了非常多经典的优秀算法,例如 BF 算法、RK 算法、BM 算法、KMP 算法,今天我介绍的主角是 BM 算法。
51 0
正则匹配起始字符串之间的文本
老是用到这个正则索性摸索了一下,试出了一个比较可靠的正则: public static string RegexReplaceStr(string regStr,string startStr,string endStr) { Regex regex = new Regex("(" + startStr + ").
687 0
字符串匹配算法
算法的改进主要是针对如果出现不匹配字符,应该怎样回退的问题 定义 在母字符串中找子字符串,如果找到返回字串在母字符串中的位置,如果没有找到,返回-1。
830 0
bbossgroups 3.0 培训教程
bbossgroups 3.0 培训教程,说不定能给你一个惊喜,目前的发布的最新版本是3.5,即将发布3.6版本,3.x版本集struts2和spring mvc 3.0的优势于一身,提供丰富的demo应用,不可小觑啊,相关的信息请参考新闻: http://www.
569 0
3402
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载