“日期处理”编程题总结

日期处理是一类令人感到头疼的编程题，这里总结下该问题的解题思路。

要解决它，必须先处理好平年和闰年，以及由此产生的二月天数不同、大月和小月等基本问题。

首先，我们可以使用一个二维数组months表示平年和闰年中每月的天数：

int month[13][2] = { { 0, 0 }, { 31, 31 }, { 28, 29 }, { 31, 31 }, { 30, 30 }, 
                    {31, 31 }, { 30, 30 }, { 31, 31 }, { 31, 31 }, { 30, 30 },
                    { 31, 31 }, {30, 30 }, { 31, 31 } };

然后，我们还需要解决平年和闰年的判别问题：

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

处理好了这些基本问题，接下来我们探讨下“日期处理”问题的各个类别及其对应的解题思路。

”日期处理“编程题大致可以分为以下几类：

求日期之间相差天数

求解这类问题有一个很直接的思路，即令日期不断加1天，直到第一个日期等于第二个日期为止。

具体做法是，如果加了1天之后天数d等于当前月份m所拥有的天数加1，那么就令月份加1，同时将天数d重置为1（即把日期变为下一个月的1号）；如果此时月份m变为了13，那么就令年份y加1，同时将月份m重置为1（即把日期变为下一年的1月）。

假设给定的两个日期分别为y1年m1月d1日、y2年m2月d2日，求解该问题的算法如下：

int count = 0;
while (y1 < y2 || m1 < m2 || d1 < d2) {
    d1++;
    if (d1 == month[m1][isLeap(y1)] + 1) {
        m1++;
        d1 = 1;
    }
    if (m1 == 13) {
        y1++;
        m1 = 1;
    }
    count++;
}

上述方法虽然简单，但可能会比较慢。如果想要加快速度，只需要先把第一个日期的年份不断加1，直到与第二个日期的年份差1为止，期间根据平年或闰年来累加365天或者366天即可。之后再进行不断令天数加1的操作。改进后的算法如下：

int count = 0;
while(y1 < y2 - 1) {
    y1++;
    count += 365;
    if(isLeap(y1)) {
        count += 1;
    }
}
while (y1 < y2 || m1 < m2 || d1 < d2) {
    d1++;
    if (d1 == month[m1][isLeap(y1)] + 1) {
        m1++;
        d1 = 1;
    }
    if (m1 == 13) {
        y1++;
        m1 = 1;
    }
    count++;
}

该问题还有另一种变体：给定一个日期和相差的天数，求该日期加上（减去）给定天数后的日期。

假设给定的日期为y年m月d日，相差的天数为days天，求解该问题的算法如下：

// 日期累加算法
// for(int i=days;i>0;i--)
while (days--) {
    d++;
    if (d == month[m][isLeap(y)] + 1) {
        m++;
        d = 1;
    }
    if (m == 13) {
        y++;
        m = 1;
    }
}

求某天是星期几

这类问题，其实可以转换为求日期之间相差天数。

具体做法是，计算给定日期y年m月d日与已知星期week的日期两者之间相差的天数days，然后让相差天数days对7取模（一周七天），求得余数r，计算r与week之间的间隔，从而得到最终的星期w。

假设已知某个日期date1是星期w1，要求日期date2（假设晚于date1）是星期w，两者相差days天，求解该问题的算法如下：

int r = days % 7;
// 这里星期日用0表示
w = (w1 + r) % 7;

若要求的日期date2早于已知日期date1，只需要按如下方式修改上面第三行代码即可。

w = (w1 - r + 7) % 7;

求某天是几月几日

给定年份和第几天，求该天是几月几号。这类问题与问题一“求日期之间相差天数”的变体十分类似。

具体做法是，从1月0日开始，每次加1天，然后调整月份（或年份），直至用完给定的天数。

假设给定的年份为year，天数为days，求解该问题的算法如下：

int m = 1, d = 0;
while (days--) {
    d++;
    if (d == month[m][isLeap(y)] + 1) {
        m++;
        d = 1;
    }
    if (m == 13) {
        y++;
        m = 1;
    }
}

参考文献

[1] 胡凡，曾磊.《算法笔记》[M].北京：机械工业出版社，2016