如果把某个数的各个数字按相反的顺序排列,得到的数和原数相同,则称这个数为“回文数”。比如123454321是一个回文数。
求用十进制、二进制、八进制表达都是回文数的所有数字,大于十进制10的最小值。
本题使用暴力搜索即可。
但是通过分析数的结构可以合理地减少有效搜索范围。
由于数的首位(最高位)的数字不能为0,因此要构成回文数,最低位的数字也不能为0。这个约束条件规则应用到十进制数就意味着该数不能被10整除,同理,该数也不能被8整除,也不能被2整除。
- # -*- 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个三重回文数了。需要对以上代码进行进一步优化。