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 年之间的有效日期。
解题思路：
leetcode连续三天模拟题，这题模拟获取输入天数到1971年1月1日的天数即可计算出星期几了。
代码：
char * dayOfTheWeek(int day, int month, int year){
char* weeks[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int days = 0;
int month_day[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
for(int i = 1971; i < year; i++)
{
if(isleapyear(i))
days += 366;
else
days += 365;
}
for(int i = 0; i < month - 1; i++)
{
if(i == 1 && isleapyear(year)) days++;
days += month_day[i];
}
days += day;
return weeks[(3 + days)%7];
}
int isleapyear(int year)
{
if((year %4 == 0 && year % 100 != 0) || year % 400 ==0) return 1;
return 0;
}
时间复杂度： O(year + month + 1)
空间复杂度： O( C )
解题方式2：
蔡勒公式
公式中的符号含义如下：
w
=
(
y
+
[
y
4
]
+
[
c
4
]
−
2
c
+
[
26
(
m
+
1
)
10
]
+
d
−
1
)
m
o
d
7
{\displaystyle w=\left(y+\left[{\frac {y}{4}}\right]+\left[{\frac {c}{4}}\right]-2c+\left[{\frac {26(m+1)}{10}}\right]+d-1\right){\bmod {7}}}
w=(y+[4y]+[4c]−2c+[1026(m+1)]+d−1)mod7
or
w
=
(
y
+
[
y
4
]
+
[
c
4
]
−
2
c
+
2
m
+
[
3
(
m
+
1
)
5
]
+
d
+
1
)
m
o
d
7
{\displaystyle w=\left(y+\left[{\frac {y}{4}}\right]+\left[{\frac {c}{4}}\right]-2c+2m+\left[{\frac {3(m+1)}{5}}\right]+d+1\right){\bmod {7}}}
w=(y+[4y]+[4c]−2c+2m+[53(m+1)]+d+1)mod7
w：星期（计算所得的数值对应的星期：0-星期日；1-星期一；2-星期二；3-星期三；4-星期四；5-星期五；6-星期六）[注 1]
c：年份前两位数
y：年份后两位数
m：月（m的取值范围为3至14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）
d：日
[ ]：称作高斯符号，代表向下取整，即，取不大于原数的最大整数。
mod：同余（这里代表括号里的答案除以7后的余数）
因为
(
y
+
[
y
4
]
+
[
c
4
]
−
2
c
+
[
26
(
m
+
1
)
10
]
+
d
−
1
)
{\displaystyle \left(y+[{\frac {y}{4}}]+[{\frac {c}{4}}]-2c+[{\frac {26(m+1)}{10}}]+d-1\right)}
(y+[4y]+[4c]−2c+[1026(m+1)]+d−1)
可能为负数，所以当出现负数的情况下不能直接mod 7。编写成代码的时候如果两个操作数中只有一个负数，求模的结果取决于机器，也就是说某些情况下w在一些机器上为负数，但是在某一些机器上w不一定为负数（例如：21%-5的结果取决于机器，可能得到1或-4），对于产生负数这种情况可将原来公式分为两步：
w
=
(
y
+
[
y
4
]
+
[
c
4
]
−
2
c
+
[
26
(
m
+
1
)
10
]
+
d
−
1
)
{\displaystyle w=\left(y+[{\frac {y}{4}}]+[{\frac {c}{4}}]-2c+[{\frac {26(m+1)}{10}}]+d-1\right)}
w=(y+[4y]+[4c]−2c+[1026(m+1)]+d−1)
w
=
(
w
%
7
+
7
)
%
7
{\displaystyle w=(w\%7+7)\%7}
w=(w%7+7)%7
若为一月二月，则看作为去年的13月和14月输入，同时在年份上减一。以上各式中的“%”符号表示取余运算。
摘自*
代码实现：
char * dayOfTheWeek(int day, int month, int year){
char* a[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
if (month == 1) {
month = 13;
year--;
}
if (month == 2) {
month = 14;
year--;
}
int y = year % 100;
int c = year / 100;
int week = (y + y/4 + c/4 - 2*c + 26*(month+1)/10 + day - 1) % 7;
week = (week%7 + 7) % 7;
return a[week];
}
时间复杂度： O(1)
空间复杂度： O(1)