写在前面
\[\mathbb Z\\ \mathbb N +\dots+,\dots,\]日期计算
日期替换
class Solution {
public:
int countTime(string time) {
if (time.find('?') == string::npos) return 1;
auto h1 = time[0], h2 = time[1];
auto m1 = time[3], m2 = time[4];
int ans1{}, ans2{};
// hour:
if (h1 == '?') {
if (h2 == '?')
ans1 = 24;
else if (h2 < '4')
ans1 = 3;
else
ans1 = 2;
} else if (h1 < '2') {
if (h2 == '?')
ans1 = 10;
else
ans1 = 1;
} else { // '2'
if (h2 == '?')
ans1 = 4;
else
ans1 = 1;
}
// min:
if (m1 == '?') {
if (m2 == '?')
ans2 = 60;
else
ans2 = 6;
} else if (m1 < '6') {
if (m2 == '?')
ans2 = 10;
else
ans2 = 1;
}
return ans1 * ans2;
}
};
或者回溯:
计算日期交集
class Solution {
public:
int countDaysTogether(string aa, string la, string ab, string lb) {
int mon[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
auto f = [&](string s) {
int m, d;
sscanf(s.c_str(), "%d-%d", &m, &d);
int ans{};
for (int i{}; i < m - 1; ++i) ans += mon[i];
return ans + d;
};
int x1 = f(aa), x2 = f(la);
int y1 = f(ab), y2 = f(lb);
return max(0, min(x2, y2) - max(x1, y1) + 1);
}
};
关键点:
- 使用 sscanf 处理字符串非常方便
- 日期转换成一年的第几天, 这样计算比较方便
- 找区间的交集只需要让两右端点的最小值减去两左端点最大值即可, 这样可以统计所有的几种可能的情况.
计算时间交集
和上一个题只能说极其相似了:
class Solution {
public:
bool haveConflict(vector<string>& event1, vector<string>& event2) {
int h1, m1, h2, m2;
sscanf(event1[0].c_str(), "%d:%d", &h1, &m1);
sscanf(event1[1].c_str(), "%d:%d", &h2, &m2);
int st1{h1 * 60 + m1}, en1{h2 * 60 + m2};
sscanf(event2[0].c_str(), "%d:%d", &h1, &m1);
sscanf(event2[1].c_str(), "%d:%d", &h2, &m2);
int st2{h1 * 60 + m1}, en2{h2 * 60 + m2};
return (min(en1, en2) - max(st1, st2)) >= 0;
}
};
事实就是还有更快的方法:
class Solution {
public:
bool haveConflict(vector<string>& event1, vector<string>& event2) {
return event1[1] >= event2[0] && event2[1] >= event1[0];
}
};
计数问题
找满足条件的计数