计算 N 以内的回数个数

2019独角兽企业重金招聘Python工程师标准>>>

若一个十进制整数按位从左向右读和从右向左读，得到的结果是相等的，就称之为回数。
即需要满足形如 abcd == dcba 这样的条件，例 121 是回数，123 不是。

请计算 N 以内回数的个数。

以上本来是我面试时出的一道代码题。它是从最早【写一个素数生成器】逐渐演化过来的，我发现他比写素数更好的地方在于还可以考察到空间变换的能力。

多数实习生和普通的程序员都可以实现 O(N) 的遍历版本，好一点的就是知道单独写一个函数进行判断，再写一个循环，可读性较好。因为招聘需求也不高，一般这样的就算过了。

只有少数人（也是小公司难约好简历吧）能对【还能再快一点么】的提问有所反应。而他们最多也就是能给出一个分治的思路，从没有人能把代码写下来，更甭提测试和debug了。所以对于这个“我自己提出的问题”，我也从没尝试过做出解答。直到昨晚面了个“历史最高分”。

那哥们看长相就是个爱写代码的，对这道题在提笔之前决定先跟我说一下他的思路：直接过掉“最蹉的方法”，描述了一个分治的思路（他是提出这个思路最快的人）。然后问我有没有更好的方法呢？他是希望从我这里得到一个指引，如果我回答是，他就去想那个答案，如果我回答否，他就开始写代码。

然后就尴尬了，因为我也不知道有没有更好的方法，甚至我都没做过这道题。。。他自己又想了大约 10min 后，决定开始实现刚才的那个思路。

他的思路是：

1. 假设题目里整数 N 一共有 x 位十进制数， 把问题分为两部分计算
2. 一部分是位数低于 x 的部分，即 0-9 的排列组合
3. 另一部分是正好 x 位整数且小于等于 N 的部分，这个比较恶心

他花半小时写完了以后也没怎么检验，而我也着急回家就简单看了一下代码，觉得没什么大问题就给过了。没管他还一幅“不行我要搜一下看别人都怎么写的”的气势。

晚上洗澡的时候我又想起这件事，觉得自己也应该做一下，万一再遇到这种较真的同学免得毫无准备。

基于上面这个思路来分析：

为了避免遍历整数，我们要从回数的自身特性上寻找规律。

回数是一个对称结构，而其每个元素都有一个大小至多为 10 的值域，所以如果我们把它当成字符串来处理，复杂度就会大大的降低。

容易发现：对于长度为 x 的整数字符串：

在每个字符的值域都是 0-9 的情况下，总共有 10**(ceil(x/2)) 种回数排列方法。（本文假设整数相除可以得到浮点数）

但有一个例外状况是，在 x > 1 时，首位不能为 0，所以公式其实是 9*10**(ceil(x/2)-1) 当 x > 1。对于 N < 10 的情况，就直接返回 N + 1 吧。

既然对于固定位数的整数，算法是这样，那么对于 x 位以内的整数，只要递归计算就可以了：

def count_palindrome_by_length(x):
	if x < 1:
		return 0
	elif x == 1:
		return 10
	else:
		return 9*(10**(ceil(x/2)-1)) + count_palindrome_by_length(x-1)

思路第二步完成。而对于思路里的第三步，就比较麻烦了。因为对小于 N 的判断，再次把处理对象拉回了整数。因为每一位的值域也不再是固定的 0-9 或 1-9，他变成动态的了，当某一位的上位还可以进位的时候，本位的值域是 0-9，否则就是 N 对应位置的那个数。例：12345 的算法并不是 1 * 3 * 4 = 12。当前两位是 11 时，第三位其实是 0-9；而当前两位是 12 时，第三位是 0-3。

从整数的角度考虑这个问题，你会发现：对于整数 abcde 的前半部分——abc来说，对于任意小于 abc (大于等于 100)的整数，将之镜像得到的回数，总是小于 abcde 的，因为这个数小于 abc00。所以最后只需要再判断 abcde 自己是不是回数就可以了。

def count_palindrome_with_fixed_length(n):
    if n < 10:
        return 10
    chars = list(str(n))
    half = chars[:int(ceil(len(chars)/2))]
    count = int(''.join(half)) - 10**(len(half) - 1)
    # 上式由此: count = (int(''.join(half)) - 1) - 10**(len(half) - 1) + 1 化简而来
    if is_palindromic(n):
        count += 1
    return count

其中 is_palindromic 是直接判断某个数字是否是回数的函数。

写到这里就会发现，原来第二步也可以使用第三步的思路来实现，进而合并为一套相同的逻辑。因为第二步的条件，不过是第三步中参数只有 9 的特殊情况罢了。感兴趣的同学可以自己组合一下，这里不再赘述。

按位算法完。

我随后Google了一下这个问题，发现除了上面这种方式以外，还有人会用一种类似筛法的东西：

def gen_palindeome(num):
    """given 12, return [121, 1221]"""
    strn = str(num)
    palindeome = []
    palindeome.append(int(strn + ''.join(reversed(strn))))
    if len(strn) > 1:
        palindeome.append(int(strn + ''.join(reversed(strn[:len(strn) - 1]))))
    return palindeome


def count_palindrome(n):
    count = 1
    for i in range(1, n + 1):
        if i<10 and is_palindromic(i):
            count += 1
        new_palindeome = gen_palindeome(i)
        for num in new_palindeome:
            if num <= n:
                count += 1
        if i > 10 and new_palindeome[-1] >= n:
            break
    return count

这种方法可读性要好得多，不过效率上却差了一大截。之所以其在计算素数上显得效率很高是因为素数的生成并不像回数那样直观，可以按位去凑。

转载于:https://my.oschina.net/lionets/blog/855783