程序员的算法趣题Q01: 回文十进制数

1. 问题描述

如果把某个数的各个数字按相反的顺序排列，得到的数和原数相同，则称这个数为“回文数”。比如123454321是一个回文数。

求用十进制、二进制、八进制表达都是回文数的所有数字，大于十进制10的最小值。

2. 解题分析

本题使用暴力搜索即可。

但是通过分析数的结构可以合理地减少有效搜索范围。

由于数的首位（最高位）的数字不能为0，因此要构成回文数，最低位的数字也不能为0。这个约束条件规则应用到十进制数就意味着该数不能被10整除，同理，该数也不能被8整除，也不能被2整除。

3. 代码和运行结果

# -*- coding: utf-8 -*-
"""
Created on Thu Aug 19 08:55:36 2021

@author: chenxy
"""
import time
import random
    
class Solution:
    def palindrome(self, N: int) -> int:
        """
        :N:    The number of the smallest palindrome to be searched for
        :    
        :ret:  return the palindrome list
        """ 
        
        count = 0
        rslt  = []
        k = 11
        while (1):            
            if not (k%8==0 or k%10==0):
                if k%1001 == 0: # cannot use 'k%1000' as print condition!
                    print('k = {0}'.format(k))
                k_decstr = str(k)
                if k_decstr == k_decstr[::-1]: # aStr[::-1] return the reverse of the original one
                    k_binstr = bin(k)[2:]  # bin(k) will return '0bxxxx'
                    if k_binstr == k_binstr[::-1]:
                        k_octstr = oct(k)[2:]  # oct(k) will return '0oxxxx'
                        if k_octstr == k_octstr[::-1]:
                            rslt.append(k)
                            count += 1
                            print('Found: k = {0}, count = {1}'.format(k, count))
                            if count == N:
                                break
            k += 2 # Skip the even number
        
        return rslt

以上代码比原题稍微延申了一点，改为寻找前N个三重回文数（即题目要求的十进制表示、二进制表示、八进制表示都是回文数）。测试运行结果如下：

if __name__ == '__main__':        
    
    sln = Solution()

    N    = 2
    t1 = time.monotonic()
    rslt = sln.palindrome(N)
    t2 = time.monotonic()    
    print('N = {0}, rslt = {1}, tCost = {2}'.format(N,rslt,(t2-t1)))  

搜索前两个三重回文数，结果非常出乎意料！

Found: k = 585, count = 1

Found: k = 719848917, count = 2

N = 2, rslt = [585, 719848917], tCost = 152.375

第2个三重回文数竟然是一个如此大的数，而且耗时长达152.375! 以这个速度没有勇气再进一步搜索第3个三重回文数了。需要对以上代码进行进一步优化。