一. 需要用到的相关知识

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

输出：

解题思路：设计日期类，通过日期类的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

输出

解题思路：

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)。

【C++】日期类题目总结

一. 需要用到的相关知识

1. 日期类实现

2. 蔡勒公式

二. 日期类题目

1、淘宝网店

2、一周中的第几天

3、美国节日

4、计算日期到天数转换题目连接

热门文章

最新文章

相关课程

相关电子书