首页
学习
活动
专区
工具
TVP
发布

“好串”求解算法优化原理与Python实现

佩服国防科大刘万伟老师的数学功底与编码功底,感谢刘老师无私分享!

=====正文=======

题目要求:称一个 0-1 串是“好串”,如果它的任何子串不在其中连续出现三次以上。编写程序,输入正整数 n,输出某个长度为 n 的好串。

在数学学上可以证明:存在任意长度的好串。事实上,若 w 是一个长度为 k 的好串,将 w 中的 0 和 1 分别替换为 01 和 10 必然是一个长度为 2k 的好串(感兴趣的读者可以用反证法证明);同时,好串的任意子串必然也是好串。

显然,单独的 0 和 1 都是好串,根据上面的性质,可以得到任意长度的好串。根据这个思路(称为“标准迭代”),可以写出下面的代码:

这个程序只有四行,算是十分短小精悍的。但是,它的可读性并不好:同时,还用到了 lambda 表达式、map 函数、字符串与列表的相互转化等十分复杂的机制;更重要的是,它的执行效率不高。

这时,应当仔细分析一下这个问题的特殊性 —— 考虑下面的 01-串序列:0、01、0110、01101001、…… (其规律为:下一个串是在上一个串的基础上添加原串的对偶串(即按位取反的串)获得)。

不难归纳证明:如果用 0 作为起始好串,上面的串列与按照标准方式迭代的序列恰好一样。

按位取反可以通过与一个全 1 序列进行异或操作得到,这样就获得了下面的代码:

细节:倒数第二行之所以需要切片操作,是因为要把异或后字串的符号位去掉。

这样,代码的效率与可读性较之于第一个版本有了大幅度的提高。但是,循环体代码里面仍然存在着进制转换、移位、求长度、切片等操作,效率仍然不是十分令人满意。同时,总感觉该问题某些特殊的性质没利用上!什么性质呢?—— 对!就是“对称性”!!!

想到了这三个字,代码的样子马上就会发生翻天覆地的变化!

这时,你可能不太相信,解决这个问题的代码竟可以简单成这样:循环体中,只存在简单的字串连接操作!

但是,冷静!这是仍然应该问一下自己:还能继续优化吗?中国传媒大学胡凤国老师敏锐的指出:这段代码跟原来比,多耗费了一倍的空间!

这的确是一个问题!怎么解决呢?事实上,串的长度每次增加一倍,这个“浪费”只出现在循环的最后一步!如果我们让循环少做一次,不就可以了吗? 终极代码如下:

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180331B0F1N200?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券