回文日期

思路

拿到这道题，先想想什么是回文日期？就是把日期写成 8 位数字 YYYYMMDD，从左读和从右读完全一样。

那关键问题来了：我们要怎么高效地找出所有回文日期？

暴力做法是枚举区间里每一天，判断它是不是回文。但日期范围可能跨很多年，逐天枚举太慢了。

换个角度想——如果 YYYYMMDD 是回文，那 8 位数字满足：d1=d8, d2=d7, d3=d6, d4=d5。也就是说，只要知道了年份 YYYY，月份和日期就完全确定了：

月份 MM = d4d3（年份第 4 位 + 第 3 位）
日期 DD = d2d1（年份第 2 位 + 第 1 位）

比如年份 2011，d1=2, d2=0, d3=1, d4=1，那 MM=11, DD=02，对应日期就是 20111102。验证一下：2-0-1-1-1-1-0-2，确实是回文。

所以思路就很清晰了：枚举年份，由年份直接算出对应的回文日期，再验证这个日期是否合法（月份 1~12、日期不超过当月天数），并且在给定区间内即可。

年份最多也就几千个，效率完全没问题。

实现步骤

读入起止日期 d1, d2，提取年份范围
枚举每个年份，由 4 位数字反推出月、日
检查月份是否在 1~12，日期是否在 1~当月最大天数
检查组合出的 8 位日期是否在 [d1, d2] 范围内
满足条件就计数

闰年判断别忘了：能被 4 整除但不能被 100 整除，或者能被 400 整除。

代码

C++
Java
Python3
JavaScript

#include <iostream>
using namespace std;

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

int daysInMonth(int y, int m) {
    int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    if (m == 2 && isLeapYear(y)) return 29;
    return days[m];
}

int main() {
    int d1, d2;
    cin >> d1 >> d2;

    int y1 = d1 / 10000, y2 = d2 / 10000;
    int count = 0;

    for (int y = y1; y <= y2; y++) {
        int d4 = y % 10;
        int d3 = (y / 10) % 10;
        int d2_ = (y / 100) % 10;
        int d1_ = (y / 1000) % 10;

        int month = d4 * 10 + d3;
        int day = d2_ * 10 + d1_;

        if (month < 1 || month > 12) continue;
        if (day < 1 || day > daysInMonth(y, month)) continue;

        int date = y * 10000 + month * 100 + day;
        if (date >= d1 && date <= d2) count++;
    }

    cout << count << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    static boolean isLeapYear(int y) {
        return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
    }

    static int daysInMonth(int y, int m) {
        int[] days = {0,31,28,31,30,31,30,31,31,30,31,30,31};
        if (m == 2 && isLeapYear(y)) return 29;
        return days[m];
    }

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

        int y1 = d1 / 10000;
        int y2 = d2 / 10000;
        int count = 0;

        for (int y = y1; y <= y2; y++) {
            int d4 = y % 10;
            int d3 = (y / 10) % 10;
            int d2_ = (y / 100) % 10;
            int d1_ = (y / 1000) % 10;

            int month = d4 * 10 + d3;
            int day = d2_ * 10 + d1_;

            if (month < 1 || month > 12) continue;
            if (day < 1 || day > daysInMonth(y, month)) continue;

            int date = y * 10000 + month * 100 + day;
            if (date >= d1 && date <= d2) count++;
        }

        System.out.println(count);
    }
}

d1 = int(input())
d2 = int(input())

def is_leap_year(y):
    return (y % 4 == 0 and y % 100 != 0) or (y % 400 == 0)

def days_in_month(y, m):
    days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    if m == 2 and is_leap_year(y):
        return 29
    return days[m]

y1 = d1 // 10000
y2 = d2 // 10000
count = 0

for y in range(y1, y2 + 1):
    d4 = y % 10
    d3 = (y // 10) % 10
    d2_ = (y // 100) % 10
    d1_ = (y // 1000) % 10

    month = d4 * 10 + d3
    day = d2_ * 10 + d1_

    if month < 1 or month > 12:
        continue
    if day < 1 or day > days_in_month(y, month):
        continue

    date = y * 10000 + month * 100 + day
    if d1 <= date <= d2:
        count += 1

print(count)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const d1 = parseInt(lines[0]);
    const d2 = parseInt(lines[1]);

    function isLeapYear(y) {
        return (y % 4 === 0 && y % 100 !== 0) || (y % 400 === 0);
    }

    function daysInMonth(y, m) {
        const days = [0,31,28,31,30,31,30,31,31,30,31,30,31];
        if (m === 2 && isLeapYear(y)) return 29;
        return days[m];
    }

    const y1 = Math.floor(d1 / 10000);
    const y2 = Math.floor(d2 / 10000);
    let count = 0;

    for (let y = y1; y <= y2; y++) {
        const d4 = y % 10;
        const d3 = Math.floor(y / 10) % 10;
        const d2_ = Math.floor(y / 100) % 10;
        const d1_ = Math.floor(y / 1000) % 10;

        const month = d4 * 10 + d3;
        const day = d2_ * 10 + d1_;

        if (month < 1 || month > 12) continue;
        if (day < 1 || day > daysInMonth(y, month)) continue;

        const date = y * 10000 + month * 100 + day;
        if (date >= d1 && date <= d2) count++;
    }

    console.log(count);
});

复杂度分析

时间复杂度: $\mathcal{O}(Y)$ ，其中 $Y$ 是年份跨度，最多几千次循环，每次 $\mathcal{O}(1)$
空间复杂度: $\mathcal{O}(1)$ ，只用了常数个变量

总结

这道题的核心在于转换思路：不要逐天枚举再判断回文，而是利用回文的对称性质，从年份直接推导出唯一可能的回文日期，再验证合法性。这样把搜索空间从几十万天压缩到了几千个年份，效率提升了两个数量级。整体代码非常简洁，就是拆数字、拼日期、校验，没有任何花哨的数据结构。

题解 | #回文日期#

回文日期

思路

实现步骤

代码

复杂度分析

总结