程序员的算法趣题Q07: 日期的二进制转换

1. 问题描述

把年月日表示为YYYYMMDD这样的8位整数，然后把这个整数转换成二进制数并逆序排列，再把得到的二进制数转换成十进制数，求与原日期一致的日期。求得的日期要在上一次东京奥运会（1964-10-10）到下一次东京奥运会（2020-07-24）之间。

2. 解题分析

其实，就是找转换为二进制数后构成了回文数（关于回文数参见<<程序员的算法趣题Q01: 回文十进制数>>）的日期。

本题的焦点之一是关于日期的处理，纯粹人工处理的话需要考虑月份大小、闰年以及二月份这种特殊月份等情况，非常容易出错。好在各种编程语言都有内置的库来做这件事情。Python中由datetime模块来处理，所以问题变成了datetime模块的使用的问题。特别是日期递增的处理方式。

焦点之二是字符串的处理。

在以下代码中，有以下几个细节值得注意（不一定是最优的，只是本渣采用了这样比较笨拙的办法而已^-^）：

1. 由date变成string后中间会有分隔符“-”（没有找到不包含“-”的字符串变换方式），需要去除。这里用str.replace()处理
2. 十进制数变成二进制数时输出的字符串，头上以“0b”开始，这个在进行是否回文数的判断中需要先去掉
3. 回文数的判断，这个采用和Q01相同的处理方式，用str[:,:,-1]的方式取字符串逆序再与原字符串比较

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Aug 26 08:35:55 2021

@author: chenxy
"""
import sys
import time
import datetime
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque

class Solution:
    def dateConversion(self, startDate: str, endDate: str) -> List:
        """
        :startDate: The state date in string format   
        :endtDate:  The end date in string format        
        :ret:       The list of dates in string format satisfying condition
        """                

        ans = []
                                                    
        # Iteration up to endDate, by increment 1 per iteration
        date = startDate
        while 1:
            # print(date)
            # Date --> string format
            dateStr  = str(date)
            # Remove '-' in the string format, for example, '1966-07-23'-->'19660723'
            dateStr1 = dateStr.replace('-','',-1)
            # Conver to integer and then to bin            
            dateBin = bin(int(dateStr1))[2:]
            if dateBin == dateBin[::-1]:
                ans.append((date))
            
            if date == endDate:
                break
            
            date += datetime.timedelta(days=1)        
        return ans

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

    tStart = time.time()
    start  = datetime.date(1964,10,10)
    end    = datetime.date(2020,7,24)
    ans    = sln.dateConversion(start,end)
    tCost  = time.time() - tStart
    print('start={0}, end={1}, tCost = {2}(sec)'.format(start,end,tCost))        
    for k in range(len(ans)):
        print('date = {0}: {1}'.format(k,ans[k]))

运行结果：

start=1964-10-10, end=2020-07-24, tCost = 0.030805349349975586(sec)

date = 0: 1966-07-13

date = 1: 1966-09-05

date = 2: 1977-02-17

date = 3: 1995-06-17

date = 4: 2002-05-05

date = 5: 2013-02-01

4. 优化

原书中提示了可以利用构成回文数的日期的特性可以大幅度削减搜索范围。当然其代价就是解决方案的可读性以及可扩展性。

To be discussed.