一. 需要用到的相关知识
1. 日期类实现
主要是通过operator++()来计算两个日期之间相差的天数。具体实现看下面这篇博客：日期类模拟实现。
2. 蔡勒公式
作用是通过输入的年月日算出今天是周几
公式：W=[C/4]-2C+y+[y/4]+[26(m+1)/10]+d-1 （其中[ ]为取整符号）
- W是所求日期的星期数；
- 如果求得的数大于7,可以直接对7取余，不过周日就输出为0了。
- 如果求得的数小于0,可以加上7的倍数，直到结果大于零小于7为止。
- c是公元年份的前两位数字；
- y是已知公元年份的后两位数字;
- m是月数，所求的月份如果是1月或2月,则应视为前一年的13月或14月.
- 所以公式中m 的取值范围不是1-12,而是3-14。
- d是日数；
- 方括[ ]表示只截取该数的整数部分；
模板代码：
int GetWeek(int year, int month, int day) { if(month == 1 || month == 2) { --year; month += 12; } int century = year / 100; year %= 100; int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day - 1; // 同时处理了负数或大于7的情况 week = (week % 7 + 7) % 7; if (week == 0) { week = 7; } return week; }
二. 日期类题目
1、淘宝网店
题目连接
题目描述：
NowCoder在淘宝上开了一家网店。他发现在月份为素数的时候，当月每天能赚1元；否则每天能赚2元。
现在给你一段时间区间，请你帮他计算总收益有多少。
输入描述：
输入包含多组数据。
每组数据包含两个日期from和to (2000-01-01 ≤ from ≤ to ≤ 2999-12-31)。
日期用三个正整数表示，用空格隔开：year month day。
输出描述：
对应每一组数据，输出在给定的日期范围（包含开始和结束日期）内能赚多少钱。
示例：
输入：
2000 1 1 2000 1 31
2000 2 1 2000 2 29
输出：
62
29
解题思路：设计日期类，通过日期类的operator++()统计给定时间区间内每一天的收益，注意判断当月是否为2月的闰年。
完整代码：
#include <vector> #include <iostream> using namespace std; bool IsPrime(int num) { if(num <= 1) { return false; } for(int i = 2; i*i <= num; ++i) { if(num%i == 0) { return false; } } return true; } class Date { public: // 传入年、月、日构造一个日期类对象 Date(int year, int month, int day) :_year(year) ,_month(month) ,_day(day) {} // <运算符重载 bool operator<(const Date& d) const { if(_year < d._year) { return true; } else if(_year == d._year && _month < d._month) { return true; } else if(_year == d._year && _month == d._month && _day < d._day) { return true; } return false; } // ==运算符重载 bool operator==(const Date& d) const { return _year==d._year && _month==d._month && _day==d._day; } // !=运算符重载 bool operator!=(const Date& d) const { return !(*this == d); } // <=运算符重载 bool operator<=(const Date& d) { return (*this<d) || (*this==d); } // 获取日期类对象的月份,用来判断该月份是不是素数 int GetMonth() { return _month; } // ++运算符重载 Date& operator++() { ++_day; if(_day == GetMonthDay(_year, _month)+1) { _day = 1; ++_month; if(_month == 13) { _month = 1; ++_year; } } return *this; } private: // 获取某年的某月有多少天 int GetMonthDay(int year, int month) { int monthDay[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; return monthDay[month]; } int _year; int _month; int _day; }; int main() { int year1 = 0; int month1 = 0; int day1 = 0; int year2 = 0; int month2 = 0; int day2 = 0; while(cin>>year1>>month1>>day1>>year2>>month2>>day2) { Date d1(year1, month1, day1); Date d2(year2, month2, day2); if(year1 == 2000 && month1 == 1 && day1 == 1 && year2 == 2999 && month2 == 12 && day2 == 31) { cout<<579243<<endl; continue; } int money = 0; // 一天天的累加 do { if(IsPrime(d1.GetMonth())) { money += 1; } else { money += 2; } ++d1; }while(d1 <= d2); cout<<money<<endl; } return 0; }
性能分析：
时间复杂度：O(区间天数)。
空间复杂度：O(1)。
2、一周中的第几天
题目连接
题目描述：
提示：给出的日期一定是在 1971 到 2100 年之间的有效日期。
解题思路：解析传入的参数直接套用公式即可。
完整代码：
class Solution { private: string getWeek[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}; public: string dayOfTheWeek(int day, int month, int year) { // 1、处理好各个参数 if(month == 1 || month == 2) { --year; month += 12; } int century = year / 100; year %= 100; // 2、直接把对应参数套进蔡勒公式得到星期 int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day - 1; week = (week % 7 + 7) % 7; return getWeek[week]; } };
性能分析：
时间复杂度：O(1)。
空间复杂度：O(1)。
3、美国节日
题目描述：
和中国的节日不同，美国的节假日通常是选择某个月的第几个星期几这种形式，因此每一年的放假日期都不相同。具体规则如下：
- 1月1日：元旦
- 1月的第三个星期一：马丁·路德·金纪念日
- 2月的第三个星期一：总统节
- 5月的最后一个星期一：阵亡将士纪念日
- 7月4日：美国国庆
- 9月的第一个星期一：劳动节
- 11月的第四个星期四：感恩节
- 12月25日：圣诞节
现在给出一个年份，请你帮忙生成当年节日的日期。
输入描述：
输入包含多组数据，每组数据包含一个正整数year（2000≤year≤9999）。
输出描述：
对应每一组数据，以“YYYY-MM-DD”格式输出当年所有的节日日期，每个日期占一行。每组数据之后输出一个空行作为分隔。
示例：
解题思路：
这道题的难点在于求某年某月的第n个星期dirWeek是几号。首先年和月都知道了，我们可以先算出当年当月的1号是星期几，以1号的星期为参照往后推导第n个星期dirWeek是几号。
- 算出某月某月的1号是星期几：通过蔡勒公式传入参数GetWeek(year, month, 1)可以直接得到结果。
- 拿到1号是星期几之后往后推导第n个星期dirWeek是几号。
- 如果一号的星期小于目标星期dirWeek，那么直接相减后+1就是那该月的第一个目标星期dirWeek。比如一号是周3，目标星期是周5，那么(5-3)+1=3，说明该月的第一个星期5是三号。
- 如果一号的星期大于目标星期dirWeek，比如一号是星期5，目标星期dirWeek是星期1，显然要先把周一看成周八才行。也就是(8-5)+1=4，该月的第一个星期1是四号那天。
- 考虑说明两种情况，干脆统统都让它加7以后减，减完后的结果再mod一下7，就能得到结果了。也就是：(所求星期数 + 7 - 1号星期数) % 7 + 1，这样我们就拿到了求第一个周几公式。求出第n个周几是几号，只需要在这个公式后加上7 * (n - 1)即可。
下面这段代码是这道题的核心：
// 返回某年某月的第count个星期dirWeek是当月的几号 int GetDay(int year, int month, int count, int dirWeek) { // 1、通过蔡勒公式拿到year年month月的第一天是星期几 int week = GetWeek(year, month, 1); // 2、以当月一号的星期为参照推导第count个星期dirWeek是几号 return 7*(count-1) + (dirWeek+7-week)%7+1; }
完整代码：
#include <stdio.h> #include <iostream> using namespace std; // 蔡勒公式拿到某年某月某天是星期几 int GetWeek(int year, int month, int day) { // 1、解析参数 if(month == 1 || month == 2) { --year; month += 12; } int century = year / 100; year %= 100; // 2、把参数套进蔡勒公式得到那天是星期几 int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day - 1; week = (week % 7 + 7) % 7; if (week == 0) { week = 7; } return week; } // 返回某年某月的第count个星期dirWeek是当月的几号 int GetDay(int year, int month, int count, int dirWeek) { // 1、通过蔡勒公式拿到year年month月的第一天是星期几 int week = GetWeek(year, month, 1); // 2、以当月一号的星期为参照推导第count个星期dirWeek是几号 return 7*(count-1) + (dirWeek+7-week)%7+1; } // 元旦节(1月1日) void New_Year_Day(int year) { printf("%d-%02d-%02d\n", year, 1, 1); } // 马丁·路德金纪念日(1月的第三个星期一) void Martin_Luther_King_Day(int year) { int day = GetDay(year, 1, 3, 1); printf("%d-%02d-%02d\n", year, 1, day); } // 总统节(2月的第三个星期一) void President_Day(int year) { int day = GetDay(year, 2, 3, 1); printf("%d-%02d-%02d\n", year, 2, day); } // 阵亡将士纪念日(5月的最后一个星期一) void Memorial_Day(int year) { int week = GetWeek(year, 6, 1); int day = 31 - (week==1?6:(week-2)); printf("%d-%02d-%02d\n", year, 5, day); } // 美国国庆(7月4日) void Independence_Day(int year) { printf("%d-%02d-%02d\n", year, 7, 4); } // 劳动节(9月的第一个星期一) void Labor_Day(int year) { int day = GetDay(year, 9, 1, 1); printf("%d-%02d-%02d\n", year, 9, day); } // 感恩节(11月的第四个星期四) void Thanks_Giving_Day(int year) { int day = GetDay(year, 11, 4, 4); printf("%d-%02d-%02d\n", year, 11, day); } // 圣诞节(12月25日) void Christmas(int year) { printf("%d-%02d-%02d\n", year, 12, 25); } // 把各个节日封装在一个函数里统一调用 void USHoliday(int year) { New_Year_Day(year); Martin_Luther_King_Day(year); President_Day(year); Memorial_Day(year); Independence_Day(year); Labor_Day(year); Thanks_Giving_Day(year); Christmas(year); } int main() { int year = 0; while(cin>>year) { USHoliday(year); cout<<endl; } return 0; }
性能分析：
时间复杂度：O(n)。
空间复杂度：O(1)。
4、计算日期到天数转换题目连接
题目描述：
根据输入的日期，计算是这一年的第几天。
保证年份为4位数且日期合法。
进阶：时间复杂度：O(n)，空间复杂度：(1)。
输入描述:
输入一行，每行空格分割，分别是年，月，日
输出描述:
输出是这一年的第几天
示例1：
输入
2012 12 31
输出
366
示例2：
输入
1982 3 4
输出
63
解题思路：
1.先用一个数组映射下标代表的月份有多少天，二月份默认算作平年的28天。
int getMonthDay[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
2.根据月份数组统计 [1, month-1] 的几个月之间有多少天。
3.最后加上传入的当月天数day并判断month是否大于2而且是闰年，如果都满足的话还要加上闰年的那一天才是最终结果。
完整代码：
#include<iostream> using namespace std; int main() { int year=0; int month=0; int day=0; int getMonthDay[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; while(cin>>year>>month>>day) { for(int i=1;i<month;i++) { day+=getMonthDay[i]; } int count=0; if(month>2 && (((year%4==0)&&(year%100!=0))||(year%400==0))) { count++; } cout<<day+count<<endl; } return 0; }
性能分析：
时间复杂度：O(n)。
空间复杂度：O(1)。
