找到给定回文日期的最近回文日期

Question

给定一个回文日期，我们必须找到与该给定日期最接近的回文日期。结果日期应在给定日期之前。

日期格式为YYYY/MM/DD。

一种蛮力解决方案是（给出伪代码，可能效率不高）。

Convert the string into a number
For each number less than this number
   If the number is a valid date then
    If number is a palindrome
         print and return

我认为一定有一些高效的算法可以解决这个问题。

例子：输入日期：2030/03/02

输出日期：2021/12/02

Answer 1

如果考虑回文日期写成YYYY/MM/DD，比如2121/12/12，可以得出一些结论：

一个月中的一天在 01 到 31 之间，一个月在 01 到 12 之间。所以你推断日期回文匹配以下正则表达式：

([0-9][0-2]|[01]3)([0-9]0|[12]1)-(0[0-9]|1[12])-([0-2][0-9]|3[01])
       1.  & 2.         3 & 4           4 & 3           2 & 1

我把重复的四个字母标出来了

输入日期之前的回文为

尽可能递减 n°4（去年和十个月前）

或

尽可能递减数字 n°3（10 年零 1 个月之前）

或

尽可能递减数字 n°2（100 年零 10 天之前）

或

如果可能的话递减数字 n°1（1000 年零 1 天之前）

或

停止

Answer 2

在给定的一年中，只有一个回文日期。因此，要找到以前的回文日期，您需要减少年份并将其转换为回文日期。

示例：对于 2030 年，有效的月份和日期将为 03 和 02，这将导致 2030/03/02。

所以，必须清楚，这种情况下的回文日期只有在以下情况下才有可能：

年份是 4 位数字（不是 10000）因为月份和天数是两位数
年份的最后两位数应为 {10, 20, 30, 40, 50, 60, 70, 80, 90, 01, 11, 21}
年份的前两位数字应该是1-31的镜像（有月份和年份的有效期）。

使用规则 2 和 3，可以在 O(1) 中检查给定年份是否具有给定格式的回文日期。让我们假设年份的有效范围是从 9999-0001，那么可以按线性顺序找到以前的回文日期。

void find_prev_date(const char* input, char * output) {
    int year = extract_year(input); //Extract first 4 digits
    --year;
    //limit is 101 because 0000 will not give you valid month and day.
    for(;year>=101;--year) {
      if(haspalindromic(year))
      {
        write_date(year, output);
      }
    }
}

bool haspalindromic(int year)
{
   int first2 = year%100;
   int last2 = year/100;
   bool second_valid = false;
   bool first_valid = false;

   switch(last2){
       case 10: case 20: case 30: case 40: case 50: case 60: case 70: case 80:
       case 90: case 1: case 11: case 21: second_valid = true; break;
   }
   if(!second_valid)
      return false;

   switch(first2) {
      case 10: case 20: case 30: case 40: case 50: case 60: case 70: case 80: case 90: case 1: case 11: case 21: case 31: case 41:    case 51: case 61: case 71: case 81: case 91:
      case 2: case 12: case 22: case 32: case 42: case 52: case 62: case 72: case 82: case 92:
      case 3: case 13:
         first_valid = true;
      break;
   }

   if(!first_valid)
      return false;

   //reverse digit such that 2 yields 20
   int month = reverse_digits_on100(last2);
   int day = reverse_digits_on100(first2);

   if(month==2) {
      if(day<=28)
         return true;
      if(isleapyear(year) && day==29)
         return true;
      if(day>28)
        return false;
   }

   switch(month) {
        case 4: case 6: case 9: case 11:
        if(day>30)
           return false;
   }
   //For remaining months, check is already made as first part of year is gives day in range of [1..31].
   return true;
}

有些功能没有实现，但名字明显暗示了意图。

找到给定回文日期的最近回文日期

find closest palindrome date of a given palindrome date

c

algorithm

palindrome