Who's Studio.

hihoCoder - 2月29日

Word count: 444Reading time: 2 min
2016/05/10

题目

给定两个日期，计算这两个日期之间有多少个2月29日（包括起始日期）。
具体描述请见hihoCoder。

解题思路

先简化问题，简化起始、终止年份，然后分情况讨论即可。

时间复杂度

时间复杂度为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

unordered_map<string, int> months;

int getMonth(string str) {
	return months[str];
}

int calYears(int start, int end) {
	if (start == end) {
		if (start % 4 == 0)
			if (start % 100 != 0 || start % 400 == 0)
				return 1;

		return 0;
	}

	int start1 = start;
	while (start1 % 4 != 0)
		start1++;
	int start2 = start1;
	while (start2 % 100 != 0)
		start2 += 4;
	int start3 = start2;
	while (start3 % 400 != 0)
		start3 += 100;

	int end1 = end;
	while (end1 % 4 != 0)
		end1--;
	int end2 = end1;
	while (end2 % 100 != 0)
		end2 -= 4;
	int end3 = end2;
	while (end3 % 400 != 0)
		end3 -= 100;

	int num1 = 0;
	if (end1 - start1 < 0)
		return 0;
	num1 = (end1 - start1) / 4 + 1;

	int num2 = 0;
	if (end2 - start2 < 0)
		num2 = 0;
	num2 = (end2 - start2) / 100 + 1;

	int num3 = 0;
	if (end3 - start3 < 0)
		num3 = 0;
	num3 = (end3 - start3) / 400 + 1;
	
	return num1 - num2 + num3;
}

int processStr(string mon, int day, int year, bool start) {
	int month = months[mon];
	if (start) {
		if (month < 2 || (month == 2 && day <= 29))
			return year;

		return year + 1;
	}
	else {
		if (month > 2 || (month == 2 && day == 29))
			return year;

		return year - 1;
	}
}

int main() {
	months["January"] = 1;
	months["February"] = 2;
	months["March"] = 3;
	months["April"] = 4;
	months["May"] = 5;
	months["June"] = 6;
	months["July"] = 7;
	months["August"] = 8;
	months["September"] = 9;
	months["October"] = 10;
	months["November"] = 11;
	months["December"] = 12;

	int T = 0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		string month;
		int day;
		string comma;
		int year;
		cin >> month >> day >> comma >> year;
		int start = processStr(month, day, year, true);
		cin >> month >> day >> comma >> year;
		int end = processStr(month, day, year, false);

		cout << "Case #" << i + 1 << ": " << calYears(start, end) << endl;
	}

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/10/2016-05-10-hihocoder-leap-year/

Publish date：May 10th 2016, 4:55:41 pm

Update date：December 4th 2022, 5:04:44 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目