算法趣题(一)

前言

从本篇文章开始,开始一系列的算法题目的学习笔记。算法的题目来源于《程序员的算法趣题》这本书,作者是日本技术作家增井敏克,只不过作者在书中实现的代码是用Ruby这门语言实现的(谁叫Ruby是日本人发明的呢~~~)。

我写这一系列文章的目的,是为了刷刷题目,提高自己的算法思维能力。还有就是,我看书的过程中,发现作者其实在一些细节方面由于语言的限制,没讲得很明白,所以我将使用目前最流行的Python语言来实现这些算法。当然了,后期也会用C语言或者Java语言实现算法。同时,我会对一些题目做一些变形,来学习算法。

每篇文章,我都会选择两道算法题目,然后对其分析,给出它的代码实现。希望我写完这一系列笔记,可以去刷LeetCode题目;也希望我的读者朋友们,从中能了解一些有趣的算法知识!

1. 回文十进制数

问题描述:求十进制、二进制、八进制表示都是回文数的所有数字中,大于10的最小数值。例如:9(十进制数)= 1001(二进制数)= 11(八进制数),这样的数字,但要找到一个大于10的最小的符合规则的数字。

分析

因为二进制数字不能以0开头,所以二进制数字首位必定是数字1,根据回文数的特点可推知,二进制数最低位也必须是1。因此最低位是1的二进制数,必定是一个奇数,继而可以排除所有的偶数可能性。

算法

从大于10的最小的奇数——11开始遍历

先判断十进制是否是回文数,再去判断二进制和十六进制是否符合

由于不确定搜索范围的上限(虽然可以定义是int最大值),所以应该用while True来达到不断循环的目的,直到找到第一个三种进制都满足回文数,当前数字就是大于10的最小的回文数,跳出循环

Python代码实现

2. 数列的四则运算

问题描述:将一个十进制四位数的每一位数字,按照原来的顺序进行加减乘除运算至少一次,使得其结果为原数字的倒序,求范围在1000 ~ 9999内满足要求的数字。例如:1314:1 * 3 + 14 = 17,或1314:131 * 4 = 524这样的组合,直到满足存在一组运算,使得1、3、1、4这四个数字的计算结果为4131。

分析

很显然,对于一个四位数而言,若要满足其结果为原来的倒序的组成的数字,就意味着倒序的结果必定是一个四位数字。

对于任何一个四位数而言,一旦出现减法和除法,这种会减少原来值的运算,肯定不可能得出新的四位数。同样的,对于加法亦是如此,因此加法在四位数与四则运算组合中,最大的可能情况是 999 + 9 = 1008,1008虽然是个四位数,但明显与范围内最大值不同。综上,只有乘法运算,才可能找到符合要求的数字。

算法

遍历1000 ~ 10000之间的所有四位数

使用 ,来实现将组合不同长度的数字,例如:1314:'1' + '' + '2' + '*' + '3' + '' + '4' = '12 * 34'

eval函数中,不允许出现数字前面带0的操作数,例如:eval("1*001"),会报错!因此,对于每个单独的数字字符串前面的0,需要删除掉!采用,函数达到删除每个数字字符串前的0

所有组合中,若最后一位数字是0,那么依据上一步算法,会将0删去。这就意味着出现数字后面带有乘号的字符串,例如:['7', '', '5*', '']组合的字符串就是 '75 *',而eval('75 *')操作是非法的!所有,必须删除所有数字字符串后面的乘号,用函数 来删除

所有组合中,可能会出现这样的情况:['7*', ' *', ' *', '1'],当数字之间含有两个乘号时,这是一个幂乘运算,不是乘法运算。所以,只能保留一个乘号,用函数 变换成乘法运算

为了防止出现这样的情况:['5', '7', '7', '5'] 5775,即四个数字中没有加入运算符,因此,需要判断字符串的长度至少大于4位,即至少插入一个运算符

Python代码实现

OneMoreThing…

今天的封面图挺好看的,但是截图似乎总是截不好,下面献上完整图片吧!

By Michael Payne From Unsplash

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180929G222IJ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券