程序员的算法趣题Q07: 日期的二进制转换
目录
1. 问题描述
把年月日表示为YYYYMMDD这样的8位整数,然后把这个整数转换成二进制数并逆序排列,再把得到的二进制数转换成十进制数,求与原日期一致的日期。求得的日期要在上一次东京奥运会(1964-10-10)到下一次东京奥运会(2020-07-24)之间。
2. 解题分析
其实,就是找转换为二进制数后构成了回文数(关于回文数参见<<程序员的算法趣题Q01: 回文十进制数>>)的日期。
本题的焦点之一是关于日期的处理,纯粹人工处理的话需要考虑月份大小、闰年以及二月份这种特殊月份等情况,非常容易出错。好在各种编程语言都有内置的库来做这件事情。Python中由datetime模块来处理,所以问题变成了datetime模块的使用的问题。特别是日期递增的处理方式。
焦点之二是字符串的处理。
在以下代码中,有以下几个细节值得注意(不一定是最优的,只是本渣采用了这样比较笨拙的办法而已^-^):
- 由date变成string后中间会有分隔符“-”(没有找到不包含“-”的字符串变换方式),需要去除。这里用str.replace()处理
- 十进制数变成二进制数时输出的字符串,头上以“0b”开始,这个在进行是否回文数的判断中需要先去掉
- 回文数的判断,这个采用和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.
上一题:Q06: 改版考拉兹猜想
下一题:Q08: 优秀的扫地机器人
本系列总目录:程序员的算法趣题:详细分析和Python全解
相关文章
- 常用元器件使用方法3:电平转换芯片74LVC1T45的使用方法[通俗易懂]
- vue格式化时间戳_日期格式转换
- char转换为数字_char字符转int
- java icu4j 全角半角转换
- js 快速将日期格式转换为时间戳
- SQL中日期与字符串互相转换操作实例
- Android常用单位转换的辅助类详解编程语言
- Oracle数据库实现金额转换大写的方法(oracle金额转大写)
- java日期格式转换大全详解编程语言
- MySQL时间戳转换为直观的日期格式(mysql时间戳转为日期)
- MySQL 日期格式转换技巧(mysql转日期格式)
- Oracle IP转换: 快速精准的解决方案(oracleip转换)
- Oracle日期格式转换:从字符串到日期的转换(oracle字符转日期)
- 轻松解决Oracle数据格式转换(oracle格式转换)
- Oracle日期转换——让你的时间格式更加灵活(oracle日期类型转换)
- MSSQL 如何将日期格式转换为需要的格式(mssql 转换日期格式)
- MSSQL中的转换函数:提高数据处理效率(mssql 转换函数)
- Oracle中Date函数的日期转换技巧(date函数oracle)
- Oracle中如何实现日期格式的转换(oracle 中日期转换)
- 转换中文日期的PHP程序
- 实现UTF8转换GB2312国标码的asp代码
- javascript日期转换时间戳转日期格式
- 用PHP实现小写金额转换大写金额的代码(精确到分)
- js时间日期和毫秒的相互转换
- Json数据转换list对象实现思路及代码
- JavaIO文件编码转换实现代码
- Oracleto_char日期转换字符串语句分享