-
每日一题：LeetCode：1185.一周中的第几天
时间：2022-01-03
力扣难度：Easy
个人难度：Easy
数据结构：整型、日期
算法：数学、模拟、基姆拉尔森公式、蔡勒公式
2022-01-03：LeetCode：1185.一周中的第几天
1. 题目描述
-
题目：原题链接
给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。
输入为三个整数：day、month 和 year，分别表示日、月、年。
您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。
-
输入输出规范
输入：整型日月年
输出：字符串周几
-
输入输出示例
输入：day = 31, month = 8, year = 2019
输出："Saturday"
2. 方法一：模拟
-
思路
首先可以得知1970年12月31日是周四，作为求解的边界
根据输入的year，month，day，计算距离1971年12月31日的总天数
所以最终求的总天数再加4对7取余，即可得到是一周的哪一天
注意每一年是否为闰年的判断，以及当年是否超过了二月
-
复杂度分析
时间复杂度：O(C)，常量级计算次数
空间复杂度：O(1)
题解
public String dayOfTheWeek(int day, int month, int year) {
String[] week = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
int[] monthDays = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int days = 4; // 初始是星期四
boolean isLeapYear = false;
for (int i = 1971; i < year; i++) {
isLeapYear = (i % 4 == 0 && i % 100 != 0) || i % 400 == 0;
days += isLeapYear ? 366 : 365;
}
for (int i = 1; i < month; i++) {
days += monthDays[i - 1];
}
isLeapYear = (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
days += (isLeapYear && month > 2) ? 1 : 0; // 当前年是否是闰年
days += day;
return week[days % 7];
}
3. 方法二：基姆拉尔森公式
-
思路
基姆拉尔森计算公式是Kim larsen calculation formula
公式：w= (d+2m+3(m+1)/5+y+y/4-y/100+y/400+1)MOD7
在公式中d表示日期中的日数，m表示月份数，y表示年数
w表示星期，w的取值范围是0~6，0表示星期日
注意：在公式中，需要把一月和二月看成是上一年的十三月和十四月，例：如果是2022-1-3则换算成：2021-13-3来代入公式计算
该公式是基于日月年分别对7取余，同时考虑闰年的影响下推导得到的
-
复杂度分析
时间复杂度：O(1)，一步到位
空间复杂度：O(1)
题解
public String dayOfTheWeek(int day, int month, int year) {
String week[] = { "Monday" , "Tuesday" , "Wednesday" , "Thursday" , "Friday" , "Saturday" , "Sunday" } ;
if ( month == 1 || month == 2 )
{
month = month + 12 ;
year -- ;
}
int index = 0 ;
//基姆拉尔森计算公式
index = ( day + 2 * month + 3 * ( month + 1 ) / 5 + year + year / 4 - year / 100 + year / 400 ) % 7 ;
return week[index] ;
}
4. 方法三：蔡勒公式
-
思路
蔡勒公式是Zeller formula，是一个计算星期的公式
公式：w = ([c/4] -2c +y +y/4 + 13*(m+1)/5 + d - 1)MOD7
如果要计算的日期是在1582年10月4日或之前，公式变为：w = ([c/4] -2c +y +y/4 + 13*(m+1)/5 + d + 1)MOD7
其中，c表示世纪，即年份除以100的结果，如果年份是公元前的年份且非整百数的话，不能整除的需要加1，如：214年是2世纪，公元前214年是前3世纪，即-3
其中，y表示年份的后两位数，如果是公元前的年份且非整百数，y应该等于cMOD100+100，如：214年的y = 14，公元前214年的y = 86
-
注意
在公式中，同样需要把一月和二月看成是上一年的十三月和十四月
该公式计算出的w可能为负数，此时需要加7来转换为正数
-
复杂度分析
时间复杂度：O(1)
空间复杂度：O(1)
题解
public String dayOfTheWeek(int day, int month, int year) {
//注意开始是周日！
String week[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
if (month < 3) {
month += 12;
year--;
}
int index = 0;
int c = year / 100;
int y = year % 100;
//蔡勒公式
index = (c / 4 - 2 * c + y + y / 4 + 13 * (month + 1) / 5 + day - 1) % 7;
return week[index < 0 ? index + 7 : index];
}
