专栏首页Python小屋“好串”求解算法优化原理与Python实现

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

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

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

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

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

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

这时,应当仔细分析一下这个问题的特殊性 —— 考虑下面的 01-串序列:0、01、0110、01101001、…… (其规律为:下一个串是在上一个串的基础上添加原串的对偶串(即按位取反的串)获得)。 不难归纳证明:如果用 0 作为起始好串,上面的串列与按照标准方式迭代的序列恰好一样。

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

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

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

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

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

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

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

----------相关阅读----------

教学课件

1900页Python系列PPT分享一:基础知识(106页)

1900页Python系列PPT分享二:Python序列(列表、元组、字典、集合)(154页)

1900页Python系列PPT分享三:选择与循环结构语法及案例(96页)

1900页Python系列PPT分享四:字符串与正则表达式(109页)

1900页Python系列PPT分享五:函数设计与应用(134页)

1900页Python系列PPT分享六:面向对象程序设计(86页)

1900页Python系列PPT分享七:文件操作(132页)

1900页Python系列PPT分享八:异常处理结构与程序调试、测试(70页)

报告PPT(163页):基于Python语言的课程群建设探讨与实践

系列题库分享

1000道Python题库系列分享一(17道)

1000道Python题库系列分享二(48道)

1000道Python题库系列分享三(30道)

1000道Python题库系列分享四(40道)

1000道Python题库系列分享五(40道)

1000道Python题库系列分享六(40道)

1000道Python题库系列分享七(30道)

1000道Python题库系列分享八(29道)

1000道Python题库系列分享九(31道)

相关技术文章

Python使用超高效算法查找所有类似123-45-67+89=100的组合

Python查找所有类似于123-45-67+89 = 100的组合

数学老师从没这么教过,乘法竖式中进位可以是多位(附Python实现与测试源码)

计算Fibonacci数列第n项的第8种方法(数学推导与Python实现)

使用Python模拟伪随机数生成原理

使用Python模拟蒙蒂霍尔悖论游戏

使用Python编写一个聪明的尼姆游戏

蒙特.卡罗方法求解圆周率近似值原理与Python实现

两行Python代码实现电影打分与推荐

Python按位异或运算符^应用案例一则:查找只出现一次的数字

本文分享自微信公众号 - Python小屋(Python_xiaowu),作者:刘万伟

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-31

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用Python处理声音文件(四):立体声音乐分离左右声道

    说明: 1、需要首先安装Python扩展库scipy。 2、本文代码只适用于未压缩的WAV声音文件。 参考代码: ? 关注“Python小屋”的所有老师、企业朋...

    Python小屋屋主
  • 淡定!不要因为纳入了高考和二级考试甚至极个别小学课程就盲目夸大Python!

    在这个自媒体超级发达或者泛滥的时代,前几天似乎一夜之间,整个朋友圈被Python纳入高考和全国计算机等级考试甚至小学信息技术课程教材的信息刷屏了,甚至一些主流媒...

    Python小屋屋主
  • 大学生们颤抖吧,中学生已经开始学Python了!

    高中生学Python?这是开玩笑的吧?高中生能学会吗?高中生学Python干啥用?高中生应该怎么学Python?高中学了Python的话大学还要再学吗? 本文我...

    Python小屋屋主
  • 用《矛盾论》来解读 Python

    大家好,我是猫哥。我对于编程语言跟其它学科的融合非常感兴趣,这种兴趣在创办公众号时就已非常浓烈,因此,几个月来,就做了不少大胆的尝试。不敢说取得了什么“成果”吧...

    Python猫
  • 用Python支持 7 亿月活用户的应用?Instagram 是这样实现的

    PyCon 简介 PyCon 是全世界最大的以 Python 编程语言 为主题的技术大会。大会由 Python 社区组织,每年举办一次。在大会上,来自世界各...

    AI研习社
  • Python进阶必读汇总

    前言 昨天翻到了一本在github开源的书: Intermediate Python. 就有了此文, 梳理了一下一些之前翻到的对python语言细节点的答案, ...

    小小科
  • 为什么要学Python编程 到底Python值不值得学

    为什么要学Python编程?到底Python值不值得学​?Python在软件质量控制、提升开发效率、可移植性、组件集成、丰富库支持等各个方面均处于先进地位。同样...

    一墨编程学习
  • 学习 Python 来做一些神奇好玩的事情吧

    相信看完 @X_AirDu 的回答我们已经对 Python 有了一个大概的了解。那接下来就让我们更深入的了解 Python 吧~

    高阳Sunny
  • 您知道 ”学习 Python 的三种境界“是什么吗?看~这里有答案!

    前言 王国维在《人间词话》中将读书分为了三种境界:“古今之成大事业、大学问者,必经过三种之境界:‘昨夜西风凋碧树,独上高楼,望尽天涯路’。此第一境也。‘衣带渐宽...

    小莹莹
  • Python语言在互联网企业应用上的十大谬误

    在接下来的文章里我将详细介绍那些使得 eBay 和 PayPal 的 Python 生态系统从2011年的不超过25个工程师到2014年超过260个工程师所使用...

    一墨编程学习

扫码关注云+社区

领取腾讯云代金券