LC 1185.Day of the Week

题目描述

这是 LeetCode 上的 1185. 一周中的第几天 ，难度为简单。

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

示例 1：

输入：day = 31, month = 8, year = 2019
输出："Saturday"

示例 2：

输入：day = 18, month = 7, year = 1999
输出："Sunday"

示例 3：

输入：day = 15, month = 8, year = 1993
输出："Sunday"

提示：

• 给出的日期一定是在 1971 到 2100 年之间的有效日期。

解答

方法一：模拟

@Source:题解来源

题目保证日期是在 1971 到 2100 之间，我们可以计算给定日期距离 1970 的最后一天（星期四）间隔了多少天，从而得知给定日期是周几。

具体的，可以先通过循环处理计算年份在 [1971,year−1] 时间段，经过了多少天（注意平年为 365，闰年为 366）；然后再处理当前年 year 的月份在 [1,month−1] 时间段 ，经过了多少天（注意当天年是否为闰年，特殊处理 2 月份），最后计算当前月 month 经过了多少天，即再增加 day 天。

得到距离 1970 的最后一天（星期四）的天数后进行取模，即可映射回答案。

class Solution {
    static String[] ss = new String[]{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
    static int[] nums = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    public String dayOfTheWeek(int day, int month, int year) {
        int ans = 4;
        for (int i = 1971; i < year; i++) {
            boolean isLeap = (i % 4 == 0 && i % 100 != 0) || i % 400 == 0;
            ans += isLeap ? 366 : 365;
        }
        for (int i = 1; i < month; i++) {
            ans += nums[i - 1];
            if (i == 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)) ans++;
        }
        ans += day;
        return ss[ans % 7];
    }
}

• 时间复杂度：\(O(C)\)，令当前时间 2100-12-xx，此时达到数据范围对应的计算量上界，设为 C 。整体复杂度为 \(O(C)\)。

• 空间复杂度：\(O(1)\)

方法二：蔡勒公式

参考蔡勒公式 - 维基百科，自由的百科全书 (wikipedia.org)。 \[ D = \lfloor \frac{c}{4} \rfloor - 2c + y + \lfloor \frac{y}{4} \rfloor + \lfloor \frac{13(m + 1)}{5}\rfloor + d - 1 \]

\[ W = D \mod 7 \]

其中：

• c 是世纪数减一，也就是年份的前两位
• y 是年份的后两位
• m 是月份。m 的取值范围为 [3, 14]，因为某年的1、2月份要看作上一年的13、14月
• d 是该月的第几天
• 除法是向下取整的除法
• 以周日为一周的第一天，也就是数组的下标为 0

由于蔡勒公式最后计算 D 可能为负数，需要处理一下。方法很多：这里由 D 计算式发现减的内容最大为 199 所以可以加上一个大于 199 且是 7 的倍数的数。我随便取一个 210 加上保证结果为正。

以下补充内容摘自百度百科。

蔡勒公式只适合于1582年（中国明朝万历十年）10月15日之后的情形。罗马教皇格里高利十三世在1582年组织了一批天文学家，根据哥白尼日心说计算出来的数据，对儒略历作了修改。将1582年10月5日到14日之间的10天宣布撤销，继10月4日之后为10月15日。 后来人们将这一新的历法称为“格里高利历”，也就是今天世界上所通用的历法，简称格里历或公历。

因此：由于历史原因以上公式仅适用于1582年10月15日及以后的情形(本题的数据范围满足此公式)，如果要计算 1582.10.4 及之前的需要修改 D 的计算式，把最后的 d - 1 改成 d + 2即可。

class Solution {
    static String[] weeks = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

    public String dayOfTheWeek(int day, int month, int year) {
        if (month < 3) {
            month += 12;
            --year;
        }
        int C = year / 100;
        int Y = year % 100;
        int idx = C / 4 - 2 * C + Y + Y / 4 + (13 * (month + 1)) / 5 + day - 1 + 210;
        return weeks[idx % 7];
    }
}

• 时间复杂度：\(O(1)\)。

• 空间复杂度：\(O(1)\)。

方法三：基姆拉尔森计算公式

这个计算公式比蔡勒公式更简单一些，不用考虑世纪数，并且不会出现负数。 根据维基百科中的说明，该公式实际上是对蔡勒公式在计算机中计算的一种常见优化，中文网站上会把这个优化公式称为 基姆拉尔森计算公式。 \[ D = y + \lfloor\frac{y}{4} \rfloor - \lfloor \frac{y}{100} \rfloor + \lfloor \frac{y}{400} \rfloor + 2m + \lfloor \frac{3(m + 1)}{5} \rfloor + d + 1 \]

\[ W = D \mod 7 \]

其中：

• c 是世纪数减一，也就是年份的前两位
• y 是年份的后两位
• m 是月份。m 的取值范围为 [3, 14]，因为某年的1、2月份要看作上一年的13、14月
• d 是该月的第几天
• 除法是向下取整的除法
• 以周日为一周的第一天，也就是数组的下标为 0

同样由于历史原因以上公式仅适用于1582年10月15日及以后的情形

class Solution {
    static String[] weeks = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

    public String dayOfTheWeek(int day, int month, int year) {
        if (month < 3) {
            month += 12;
            --year;
        }
        int idx = year + year / 4 - year / 100 + year / 400 + 2 * month + (3 * (month + 1)) / 5 + day + 1;
        return weeks[idx % 7];
    }
}

• 时间复杂度：\(O(1)\)。

• 空间复杂度：\(O(1)\)。

每题一图