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

题目：不一样的逆序数

时间限制： 3000MS

内存限制： 589824KB

题目描述

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

输入描述

单组输入。

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

输出描述

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

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

样例输入

10000

样例输出

1
2178 8712

提示

在本题目的情景中我们认为：1234的逆序数为4321，1100的逆序数为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*x 和 x 的逆序数相等这个 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()