[LeetCode] 1185. Day of the Week

[grandyang]

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"

Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"

Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

Constraints:

• The given dates are valid dates between the years 1971 and 2100.

这道题给定了一个任意的年月日，让求该日期是星期几。博主最开始想的方法是需要知道一个特定的日期是星期几，然后推算给定的日期跟这一天相差的天数，从而推算出给定的日期是星期几。由于限定了年份不早于 1971 年，则可以用 1970 年 12 月 31 日这个当作确定日期，通过查询得知为星期四，那么 1971 年1月1日距离这个确定日期为1天，则应该为星期五，在星期数组中坐标应该为5，注意是以 Sunday 开始的。所以天数应该初始化为4（作为偏移量），然后再计算给定天数跟 1970 年 12 月 31 日的距离天数。首先应该确定给定的年份距离 1971 有多少年，因为完整的年份比较好计算天数，若给定的就是 1971 年，则距离 1971 为0年，没有完整的年份。完整的年份一般为 365 天，除了闰年需要多加一天，所以还需要对于每个年份都判定一下是否是闰年，是的话就多加一天。接下来，要统计完整的月份数，可以用一个数组列出每个月的具体天数，统计出了完整的月份，直接查表将其对应的天数加上，还是需要考虑闰年的情况，因为闰年的二月会多一天。最后直接加上天数，这样距离 1970 年 12 月 31 日的总天数就算出来了，直接对7取余，并查表就可以得到是星期几了（由于总天数开始初始化为4，相当于已经考虑偏移了），参见代码如下：

解法一：

class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        int totalDays = 4;
        vector<int> monthDays{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        vector<string> days{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        for (int i = 1971; i < year; ++i) {
            totalDays += isLeapYear(i) ? 366 : 365;
        }
        for (int i = 1; i < month; ++i) {
            totalDays += monthDays[i];
        }
        if (month > 2 && isLeapYear(year)) ++totalDays;
        totalDays += day;
        return days[totalDays % 7];
    }
    bool isLeapYear(int year) {
        return year % 400 == 0 || (year % 100 != 0 && year % 4 == 0);
    }
};

上面的解法虽然可以通过 OJ，但是有点太不高效了，对于这种求某个日期的星期几的问题，有非常高效的算法或公式可以快速求的，比如蔡勒公式 Zeller Formula，就可以把年月日当参数带入一个公式来直接求得星期几，具体可以参见这个贴子，需要注意的是年和月需要预处理一下，在蔡勒公式中，某年的1、2月要看作上一年的 13、14 月来计算，比如 2003 年1月1日要看作 2002 年的 13 月1日来计算，参见代码如下：

解法二：

// Zeller Formula
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        vector<string> days{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        if (month < 3) month += 12, year -= 1;
        int c = year / 100, y = year % 100, m = month, d = day;
        int w = (c / 4 - 2 * c + y + y / 4 + 13 * (m + 1) / 5 + d - 1) % 7;
        return days[(w + 7) % 7];
    }
};

还有一种方法也可以快速计算星期几，叫做坂本算法 Sakamoto Algorithm，这样一个牛逼闪闪的算法会不会是《在下坂本，有何贵干？！》中的逼王-坂本童鞋发明的呢，哈哈，开玩笑～ 其实本质上跟上面的蔡勒公式还是很像的，不过写法略有不同，注意这里用了一个月份偏移数组t，是通过 (13(m+1)/5)%7 计算来的，其中 (March=1,…,February=12)，这么一看是不是就上面的蔡勒公式本质是一样了，关于这个算法可以参见维基百科上的这个贴子，参见代码如下：

解法三：

// Sakamoto Algorithm
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        vector<string> days{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        vector<int> t{0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
        if (month < 3) year -= 1;
        return days[(year + (year / 4 - year / 100 + year / 400) + t[month - 1] + day) % 7];
    }
};

Github 同步地址:

#1185

参考资料：

https://leetcode.com/problems/day-of-the-week/

https://leetcode.com/problems/day-of-the-week/discuss/377384/JavaC%2B%2BPython-Zeller-Formula

https://leetcode.com/problems/day-of-the-week/discuss/381894/JavaC%2B%2BPython3-Sakamoto-Algorithm

LeetCode All in One 题目讲解汇总(持续更新中...)