算法分析

由于题目要求在指定的日期范围内找出回文日期的个数
可转换为
前四位是从1000遍历到9999，通过翻转得到一个特定的回文日期，判断该回文日期是否符合条件，若符合则表示找到在指定的日期范围内找到一个回文日期

步骤

• 1、先枚举回文数

• 2、判断是否在指定范围内

• 3、判断日期是否合法
  注意：

  • (1)由于日期具有单调递增性，则date1 <= date <= date2,表示当前日期在指定范围内

  • (2)如何判断是闰年还是平年

    • 普通闰年:公历年份是4的倍数的，且不是100的倍数，为闰年。

    • 世纪闰年:公历年份是整百数的，必须是400的倍数才是世纪闰年

时间复杂度 $O(10^4)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int[] days = new int[]{0,31,28,31,30,31,30,31,31,30,31,30,31};
    static boolean check(int date)
    {
        int year = date / 10000;
        int month = date % 10000 / 100;
        int day = date % 100;
        if(month == 0 || month > 12) return false;
        if(day == 0 || month != 2 && day > days[month]) return false;

        if(month == 2)
        {
            int leap = 0;//0表示平年，1表示闰年
            if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
                leap = 1;
            if(day > 28 + leap) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int date1 = scan.nextInt();
        int date2 = scan.nextInt();
        int res = 0;
        for(int i = 1000;i < 10000;i++)
        {
            int date = i,x = i;
            //date 表示 前四位翻转后变成八位的数字
            for(int j = 1;j <= 4;j++)
            {
                date = date * 10 + x % 10;
                x /= 10;
            }
            if(date1 <= date && date <= date2 && check(date)) res ++;
        }
        System.out.println(res);
    }
}