美团笔试题 - 不一样的逆序数

本文最后更新于:2020年8月15日 晚上

题目:不一样的逆序数

时间限制: 3000MS

内存限制: 589824KB

题目描述

小团最近对逆序数(将一个数字逐位逆序,例如1234的逆序数为4321)特别感兴趣,但是又觉得普通的逆序数问题有点太乏味了。于是他想出了一个新的定义:如果一个数的4倍恰好是它的逆序数,那么称这两个数是新定义下的逆序对。接下来给定一正整数n,问:不超过n的正整数中有多少对新定义下的逆序对?

输入描述

单组输入。

输入一个正整数n,n<1e7。

输出描述

第一行输出在不超过n的前提下有多少对逆序数,接下来每一行输出一对逆序数,以空格分隔。如果有多组逆序数,按照第一个数升序输出。

如果没有一对逆序数则直接输出0即可。

样例输入

10000

样例输出

1
2178 8712

提示

在本题目的情景中我们认为:1234的逆序数为43211100的逆序数为11

解题思路

其实这种题,思路并不难,暴力解遍历加判断就可以解决!

但也显然的,这题为的就是让我们剔除大多数的无用数据,以更高的效率解题,直接遍历会超时的~

很遗憾我笔试过程中真就没想出来怎么去剔除无用数据,不过笔试结束后仔细想了想,还是发现了一些规律。我们学过数学有点基础都知道,乘法运算末位数直接关系到结果的末位数,就从这一点入手,列表观察一下:

以x结尾的数: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
4*x的末位数: 0, 4, 8, 2, 6, 0, 4, 8, 2, 6

这时候再考虑一下题目要找的是 4*xx 的逆序数相等这个 x ,那我们现在根据上面的规律再观察一下逆序数呢~

以x结尾的数: 0xx0, 4xx1, 8xx2, 2xx3, 6xx4, 0xx5, 4xx6, 8xx7, 2xx8, 6xx9
4*x的末位数: 0xx0, 1xx4, 2xx8, 3xx2, 4xx6, 5xx0, 6xx4, 7xx8, 8xx2, 9xx6

看到这儿,是不是有头绪了,我们来分析一下:

  1. 以0结尾的数必然以0开头,但是怎么可能有以0开头的正整数呢,所以可以直接排除所有以0结尾的数;
  2. 再来看以1结尾的数,乘以4倍后必然以4结尾,如果这个数满足条件,那么它肯定以4开头,问题就来了,正整数4xx1乘了4倍以后怎么可能得到相同位数的比它自身小的1xx4,所以所有以1结尾的数也可以直接排除;
  3. 再看以3结尾的数,同上可知原数必然是2xx3的形式,而它的逆序数必然是3xx2,虽然不再小于原数,但是它们位数相等的情况下,2xx3乘以4以后至少也大于8xx2啊,所以所有以3结尾的数也可以直接排除;
  4. 其实同样的方法分析之后可以知道,第一种类型的有[0, 5],第二种类型的有[1, 2, 4, 7],第三种类型的有[3, 6, 9];
  5. 只有以8结尾的数是可能找到符合条件的数的,只有2xx8乘以4可能得到8xx2。

都分析到这一步了就太简单了,只需要在遍历的时候只遍历以8结尾的数即可,以python为例可以这样 for n in range(8, num + 1, 10) ,不过还可以再过滤掉一些,因为有了以上的基础,可以很容易得到第一个符合条件的正整数是 2178 ,也就是说2178之前的数也是没必要遍历的,如果输入的正整数 n < 2178 ,那么按照题意直接打印 '0' 即可。

注:写到这里,我发现自己竟然遗漏了一些东西,其实根据上面的分析,可能的数据必然是2xx8的形式,所以还应该筛选一下以2开头的数,只需要做一点小小的更改就可以了,改进后的代码也放在后面源码二中了。

源码一

def inverse_number():
    num = int(input())
    # 不存在小于8的符合条件的正整数
    if num < 8:
        print(0)
        return
    exist = False  # 是否存在符合条件的逆序数
    # 影响性能最关键的一步,从8开始,到num结束,步长为10
    for n in range(2178, num + 1, 10):
        rev = int(str(n)[::-1])  # n的逆序数
        n4 = 4 * n  # n的4倍
        if n4 == rev:
            exist = True
            print(str(n) + ' ' + str(rev))
    if not exist:
        print(0)


if __name__ == '__main__':
    inverse_number()

源码二

def inverse_number():
    num = int(input())
    # 不存在小于8的符合条件的正整数
    if num < 8:
        print(0)
        return
    exist = False  # 是否存在符合条件的逆序数
    digits = 3  # 位数
    # 影响性能最关键的一步,从8开始,到num结束,步长为10
    n = 2178  # 从2178开始,第一个符合条件的数
    while n < num + 1:
        # 过滤掉非2开头的数
        if n > 3 * pow(10, digits):
            digits += 1
            n = 2 * pow(10, digits) + 8  # 保持以2开头以8结尾
            continue
        rev = int(str(n)[::-1])  # n的逆序数
        n4 = 4 * n  # n的4倍
        if n4 == rev:
            exist = True
            print(str(n) + ' ' + str(rev))
        n += 10
    if not exist:
        print(0)


if __name__ == '__main__':
    inverse_number()