-
每日一题: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];
}