112. 跳跃数(Bouncy numbers)

一个数字如果从左往右数,左边的数字都不比右边的数字大,那么这个数就称之为递增数,比如说数字134468;同理,如果一个数字从左往右数,左边的数字都不比右边的数小,这样的数就称之为递减数,比如说数字66420。我们把既不是递增数与是递减数的正整数称之为跳跃数,比如说数字155349。

很明显,一百以下的数字中不会有跳跃数,但是在一千以下有超过一半(525)的数字是跳跃数。事实上,跳跃数占比刚好超过50%的数字是538。奇怪的是,随着数字增大跳跃数会越来越常见,增加到数字21780时,跳跃数的比例刚好等于90%。试求跳跃数比例刚好达到99%时的最小数字。

分析:这道题目的核心是找到一个判断某个数字是否是跳跃数的方法,我使用的方法是将一个数转化成它各位数字字符串对应的列表\(lst\),然后对这个数字列表中的各位数字字符串进行从小到大排序形成列表\(sort\)。如果一个数字是递增数,那么\(lst\)\(sort\)应该相等;反之,如果一个数字是递减数,那么\(lst\)的翻转和\(sort\)相等;如果两种情况都不满足,那么这个数字就是一个跳跃数。

当判断是否为跳跃数的方法确定后,我们只需要从一百往上搜索,判断每个数是否为跳跃数,然后计算截至到目前为跳跃数的多少占所有数字的比例,直到这个比例达到99%时,返回这个数字即为题目所求。代码如下:

# time cost = 2.79 s ± 10.9 ms

from itertools import count

def is_bouncy_number(n):
    sort = sorted(str(n))
    lst = list(str(n))
    if sort == lst or sort == lst[::-1]:
        return False
    else:
        return True

def main(pert=0.99):
    n = 0
    for i in count(100,1):
        if is_bouncy_number(i):
            n = n + 1
            if n/i >= pert:
                return i