要找出“完全对称日”,我们得先明确一下这个概念。在大多数情况下,人们说的“完全对称日”是指在日期表示法中,正着读和倒着读都一样,比如2021年12月2日(20211202)。当然,日期表示法有很多种,比如公历的年月日、月日年,或者加上星期几等等。咱们就以最常见的公历年月日“YYYYMMDD”格式为基础来聊聊,看怎么能快速找出这类日子。
什么是“完全对称日”(Palindrome Day)?
简单来说,就是年月日连起来写,比如20211202,是一个回文数。
为什么需要“算法”?
如果你只是想找几个例子,手算或者随便翻翻日历就能找到了。但如果我们要“找出所有”,而且是“很快”,那肯定得依赖程序和算法了。毕竟,一年有365天(闰年366天),百年千年算下来,手动查验效率太低了。
核心思路:生成与校验
找出这类对称日,最直接的思路就是:
1. 生成可能对称的日期结构: 利用日期的回文特性,反推出可能的年月日组合。
2. 校验生成的日期是否真实存在: 看看这些反推出来的年月日组合,在现实日历里是不是真的有这一天。
一种直观但效率不高的“暴力”方法:
我们可以从一个很远的过去(比如公元1年)或者一个我们确定的起点,一直往后推,每天都检查一下它是不是对称日。
过程:
从某个日期(比如 00010101)开始。
将日期格式化成YYYYMMDD(例如 00010101)。
检查这个字符串是不是回文。
如果是,记录下来。
然后日期加一天,重复步骤。
为什么效率不高?
大部分日期都不是对称日,我们做了大量的无效检查。
我们需要处理日期的递增(30天进1个月,12个月进1年,闰年处理)。
更“智能”的方法:基于回文结构的生成
既然我们知道目标是回文,我们可以直接“制造”回文,然后验证。
以 YYYYMMDD 为例:
1. 选择年份(YYYY): 年份是4位数,这是我们主要的“生成器”。我们可以遍历一个范围的年份。
2. 构造回文的月份(MM)和日期(DD):
假设我们选定了年份 YYYY。
YYYY 的后两位数字,就是我们回文的 MM 的前两位。
YYYY 的前两位数字,就是我们回文的 DD 的后两位。
具体操作:
将年份 YYYY 转换为字符串。
取 YYYY 的后两位,作为 M1M2。
取 YYYY 的前两位,作为 Y1Y2。
反转 Y1Y2,得到 D2D1。
那么,潜在的日期就是 YYYY M1M2 D2D1。
举例:
年份: 2021
YYYY 字符串: "2021"
后两位(MM 的前两位): "21" > 那么 MM 可能是 "21" (但一个月最多31天,所以这里需要反过来想)
让我们换个更清晰的思路:
我们知道 YYYYMMDD 是一个回文。
Y1 Y2 Y3 Y4 M1 M2 D1 D2
回文意味着: Y1 = D2, Y2 = D1, Y3 = M2, Y4 = M1
所以,如果我们知道年份 YYYY,我们就可以直接构造出潜在的 M 和 D:
年份 YYYY (例如 2021)
Y1=2, Y2=0, Y3=2, Y4=1
月份 MM 的 M1 应该是 Y4,M2 应该是 Y3。所以 MM = Y4Y3。
在这个例子中: M1=1, M2=2。所以 MM = 12。
日期 DD 的 D1 应该是 Y2,D2 应该是 Y1。所以 DD = Y2Y1。
在这个例子中: D1=0, D2=2。所以 DD = 02。
结果: 2021 年 12 月 02 日。
算法步骤(改进版):
1. 设定年份范围: 确定我们要搜索的年份区间(例如,从1000年到9999年,或者从1900年到2099年)。
2. 遍历年份: 对范围内的每一个年份 `YYYY` 进行处理。
3. 构造潜在的月份和日期:
将 `YYYY` 转换为字符串,例如 `sYYYY`。
反转 `sYYYY` 得到 `sYYYY_rev`。
取 `sYYYY_rev` 的前两位作为潜在的月份 `MM_str`。
取 `sYYYY_rev` 的后两位作为潜在的日期 `DD_str`。
4. 组合成日期字符串: 形成 `YYYYMM_strDD_str`。
5. 校验日期有效性:
将 `MM_str` 和 `DD_str` 转换为整数,得到 `month` 和 `day`。
检查月份: `1 <= month <= 12`。
检查日期: `1 <= day <= max_days_in_month(month, year)`。这里需要考虑闰年。
`max_days_in_month(month, year)` 函数需要知道当前年份 `year` 是否是闰年。
闰年判断:能被4整除但不能被100整除,或者能被400整除。
如果月份和日期都有效: 那么 `YYYYMM_strDD_str` 就是一个完全对称日。记录下来。
举例说明:
年份: 2021
`sYYYY` = "2021"
`sYYYY_rev` = "1202"
`MM_str` = "12" (取 "1202" 的前两位)
`DD_str` = "02" (取 "1202" 的后两位)
校验:
`month` = 12 (有效,1 <= 12 <= 12)
`day` = 02 (有效,1 <= 2 <= 31,12月有31天)
结果: 20211202 是一个完全对称日。
年份: 2112
`sYYYY` = "2112"
`sYYYY_rev` = "2112"
`MM_str` = "21" (取 "2112" 的前两位)
`DD_str` = "12" (取 "2112" 的后两位)
校验:
`month` = 21 (无效,大于12)
结果: 21122112 不是一个有效的日期。
年份: 2001
`sYYYY` = "2001"
`sYYYY_rev` = "1002"
`MM_str` = "10"
`DD_str` = "02"
校验:
`month` = 10 (有效)
`day` = 02 (有效,10月有31天)
结果: 20011002 是一个完全对称日。
年份: 2110
`sYYYY` = "2110"
`sYYYY_rev` = "0112"
`MM_str` = "01"
`DD_str` = "12"
校验:
`month` = 01 (有效)
`day` = 12 (有效,1月有31天)
结果: 21100112 是一个完全对称日。
关于“很快”的进一步优化:
上面的算法已经相当快了,因为它直接“生成”候选者。搜索一个千年(1000年到1999年)只需要1000次反转和1000次校验,这在计算机看来几乎是瞬时的。
如果考虑其他日期格式呢?
MMDDYYYY:
MM DD YYYY
M1 M2 D1 D2 Y1 Y2 Y3 Y4
回文:M1=Y4, M2=Y3, D1=Y2, D2=Y1, Y1=D2, Y2=D1, Y3=M2, Y4=M1。
这要求 M1=Y4, M2=Y3, D1=Y2, D2=Y1 并且 Y1=D2, Y2=D1, Y3=M2, Y4=M1。
代入: Y1=Y1, Y2=Y2, Y3=Y3, Y4=Y4。
这意味着 YYYY 必须是 DD 的反转,MMDD 必须是 YYYY 的反转。
例如,MMDD YYYY = 12022021。
MMDD = "1202" > MM=12, DD=02
YYYY = "2021"
YYYY 的反转 = "1202"
MMDD = YYYY 的反转。
生成方法: 选取一个年份 YYYY,反转得到 YYYY_rev。如果 YYYY_rev 的前两位是有效的月份,后两位是有效的日期,那么 MMDDYYYY 就是一个对称日。
年份 2021 > YYYY_rev = "1202" > MM=12, DD=02。 20211202 (DDMMYYYY)
年份 2021 > YYYY_rev = "1202" > MM=12, DD=02。 12022021 (MMDDYYYY)
这说明,相同的数字序列,在不同的格式下可能产生不同的对称日。
DDMMYYYY:
DD MM YYYY
D1 D2 M1 M2 Y1 Y2 Y3 Y4
回文:D1=Y4, D2=Y3, M1=Y2, M2=Y1。
生成方法: 选取年份 YYYY。
Y1 Y2 Y3 Y4
D1 = Y4, D2 = Y3 > DD = Y4Y3
M1 = Y2, M2 = Y1 > MM = Y2Y1
结果: Y4Y3 Y2Y1 Y1Y2Y3Y4
举例:
年份:2021
Y1=2, Y2=0, Y3=2, Y4=1
DD = Y4Y3 = 12
MM = Y2Y1 = 02
结果: 12022021 (DDMMYYYY)
校验: 12月02日 2021年 (有效)
结论:
要“很快”找出所有完全对称日,关键在于 “生成校验” 的策略,而不是“遍历校验”。通过利用日期的回文结构,我们可以直接从年份 YYYY 推算出潜在的月份 MM 和日期 DD,然后只需进行有效的日期校验即可。
对于 YYYYMMDD 格式: 遍历年份 YYYY,将其反转,取反转后的前两位作 MM,后两位作 DD,然后校验 MM 和 DD 的有效性。
对于 DDMMYYYY 格式: 遍历年份 YYYY,取 YYYY 的后两位作 DD,Y 的前两位反转作 MM,然后校验。
算法实现细节:
日期校验函数: 编写一个健壮的函数 `isValidDate(year, month, day)`,能够正确处理不同月份的天数以及闰年。
字符串处理: 利用编程语言提供的字符串反转、截取功能。
数据类型: 年、月、日需要用整数存储,但生成过程可以先用字符串。
这种生成模式的算法,在计算机处理能力下,几乎是瞬时的,远比按天检查来得“快”。你可以轻松地生成一个百年、千年甚至万年的所有对称日列表。