题解 | #回文日期#

题目链接

题目描述

一个日期用8位数字 YYYYMMDD 表示。若这个8位数字本身是一个回文数，则称该日期为“回文日期”。给定一个起始日期 date1 和一个终止日期 date2，请计算这个区间内（包含 date1 和 date2）所有真实存在的回文日期的数量。

日期合法性规则：

月必须在1-12之间。
日必须合法（例如1月最多31天，平年2月最多28天）。
闰年判定：能被4整除但不能被100整除，或者能被400整除的年份为闰年。闰年2月有29天。

解题思路

本题要求在给定范围内寻找所有合法的回文日期。如果逐一遍历从起始日期到终止日期的每一天，判断其是否回文，效率会非常低下，因为日期范围可能很大。

一个更高效的策略是生成回文数，再验证其合法性。

一个8位的回文日期 YYYYMMDD 必然满足 MMDD 是 YYYY 的倒序。例如，如果年份是 2011，其倒序是 1102，那么构成的回文日期就是 20111102，即2011年11月02日。

基于这个特性，我们的算法可以设计如下：

确定年份范围：从输入的起始日期和终止日期中，提取出起始年份 start_year 和终止年份 end_year。
遍历年份生成候选日期：
- 我们只需要遍历从 start_year 到 end_year 的每一个年份 y。
- 对于每个年份 y，我们将其四位数字倒序，得到对应的月份 m 和日期 d。
  - 例如，若 y = abcd，则 m = dc，d = ba。
验证候选日期的合法性：
- 日期有效性：检查 (y, m, d) 是否是一个真实存在的日期。这需要一个辅助函数 isValidDate(y, m, d) 来判断：
  - m 是否在 1 到 12 之间。
  - d 是否在 1 到该月的最大天数之间（需要考虑 y 是否为闰年）。
- 范围有效性：如果日期有效，我们将 y, m, d 组合成一个8位整数 palindrome_date。然后检查这个数是否落在给定的 [startDate, endDate] 区间内。
计数：如果一个候选日期同时满足上述两个有效性条件，则我们的计数器加一。
输出结果：遍历完所有年份后，输出最终的计数值。

这个方法将搜索空间从巨大的日期范围缩小到了几千个年份，大大提高了效率。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

bool isValidDate(int y, int m, int d) {
    if (m < 1 || m > 12 || d < 1) {
        return false;
    }
    int days_in_month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (isLeap(y)) {
        days_in_month[2] = 29;
    }
    return d <= days_in_month[m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int start_date, end_date;
    cin >> start_date >> end_date;

    int start_year = start_date / 10000;
    int end_year = end_date / 10000;
    int count = 0;

    for (int y = start_year; y <= end_year; ++y) {
        string y_str = to_string(y);
        string rev_y_str = y_str;
        reverse(rev_y_str.begin(), rev_y_str.end());

        int m = stoi(rev_y_str.substr(0, 2));
        int d = stoi(rev_y_str.substr(2, 4));

        if (isValidDate(y, m, d)) {
            int palindrome_date = y * 10000 + m * 100 + d;
            if (palindrome_date >= start_date && palindrome_date <= end_date) {
                count++;
            }
        }
    }

    cout << count << endl;

    return 0;
}

import java.util.Scanner;

public class Main {

    private static boolean isLeap(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }

    private static boolean isValidDate(int y, int m, int d) {
        if (m < 1 || m > 12 || d < 1) {
            return false;
        }
        int[] daysInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if (isLeap(y)) {
            daysInMonth[2] = 29;
        }
        return d <= daysInMonth[m];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int startDate = sc.nextInt();
        int endDate = sc.nextInt();

        int startYear = startDate / 10000;
        int endYear = endDate / 10000;
        int count = 0;

        for (int y = startYear; y <= endYear; y++) {
            String yStr = String.format("%04d", y);
            String revYStr = new StringBuilder(yStr).reverse().toString();

            int m = Integer.parseInt(revYStr.substring(0, 2));
            int d = Integer.parseInt(revYStr.substring(2, 4));

            if (isValidDate(y, m, d)) {
                int palindromeDate = Integer.parseInt(yStr + revYStr);
                if (palindromeDate >= startDate && palindromeDate <= endDate) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

def is_leap(year):
    return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

def is_valid_date(y, m, d):
    if not (1 <= m <= 12 and 1 <= d <= 31):
        return False
    
    days_in_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    if is_leap(y):
        days_in_month[2] = 29
        
    return d <= days_in_month[m]

start_date_str = input()
end_date_str = input()

start_date = int(start_date_str)
end_date = int(end_date_str)

start_year = int(start_date_str[:4])
end_year = int(end_date_str[:4])
count = 0

for y in range(start_year, end_year + 1):
    y_str = str(y).zfill(4)
    rev_y_str = y_str[::-1]
    
    m = int(rev_y_str[:2])
    d = int(rev_y_str[2:])

    if is_valid_date(y, m, d):
        palindrome_date_str = y_str + rev_y_str
        palindrome_date = int(palindrome_date_str)
        if start_date <= palindrome_date <= end_date:
            count += 1
            
print(count)

算法及复杂度

算法：枚举 + 模拟
时间复杂度：设起始和终止年份的差距为 $K$ 。我们对这 $K$ 个年份进行遍历，每次遍历执行常数时间的操作（字符串转换、合法性判断）。因此，总时间复杂度为 $\mathcal{O}(K)$ 。
空间复杂度： $\mathcal{O}(1)$ ，仅使用了常数个变量来存储日期和计数。