算法基础算法

日期和时间

字数统计: 2.3k字   |   阅读时长: 11分
, ,

摘要: 力扣上日期和时间相关题目汇总

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对日期和时间的处理是在编程中经常要处理的问题。本文我们总结力扣上与日期和时间有关的题目。由于不涉及什么算法，因此每道题直接给出代码。以下是总览：

在日期和时间的处理中，经常需要判断闰年，下面是判断的代码。后面的题目的代码中直接用 is_leap_year。

1
2
3
4
5
6
7
8
9
bool is_leap_year(int year)
{
    // 四年一闰,百年不闰,四百年再闰
    if(year % 4 != 0)
        return false;
    if(year % 100 == 0 && year % 400 != 0)
        return false;
    return true;
}

$1 星期

1185. 一周中的第几天

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}。

代码 (c++)

1
W = [Y-1] + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + D

Y 是年份数，D 是这一天在这一年中的累积天数。

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
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        vector<int> months = {
            31, -1, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
        };
        vector<string> result = {
            "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"
        };
        if(is_leap_year(year))
            months[1] = 29;
        else
            months[1] = 28;
        int iter = s_ans - 1;
        for(int y = s_year; y < year; ++y)
        {
            if(is_leap_year(y))
                iter = (iter + 366) % 7;
            else
                iter = (iter + 365) % 7;
        }
        for(int m = s_month; m < month; ++m)
        {
            iter = (iter + months[m - 1]) % 7;
        }
        iter = (iter + day) % 7;
        return result[iter];
    }

private:
    const int s_year = 1971;
    const int s_month = 1;
    const int s_day = 1;
    const int s_ans = 4;
};

$2 天

1118. 一月有多少天

指定年份 Y 和月份 M，请你帮忙计算出该月一共有多少天。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numberOfDays(int Y, int M) {
        vector<int> months({31, -1, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31});
        if(is_leap_year(Y))
            months[1] = 29;
        else
            months[1] = 28;
        return months[M - 1];
    }
};

1154. 一年中的第几天

给你一个按 YYYY-MM-DD 格式表示日期的字符串 date，请你计算并返回该日期是当年的第几天。

通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。每个月的天数与现行公元纪年法（格里高利历）一致。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int dayOfYear(string date) {
        int y, m, d;
        stringstream ss;
        ss << date.substr(0, 4) + ' ';
        ss << date.substr(5, 2) + ' ';
        ss << date.substr(8, 2);
        ss >> y;
        ss >> m;
        ss >> d;
        vector<int> months({31, -1, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31});
        if(is_leap_year(y))
            months[1] = 29;
        else
            months[1] = 28;
        int result = 0;
        for(int i = 1; i < m; ++i)
            result += months[i - 1];
        result += d;
        return result;
    }
};

1360. 日期之间隔几天

请你编写一个程序来计算两个日期之间隔了多少天。

日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。

代码 (C++)

首先抽象出几个组件进行实现。

  • “YYYY-MM-DD” 转 (y,m,d)
1
2
3
4
5
6
7
8
9
10
void get_ymd(const string& date, int& y, int& m, int& d)
{
    stringstream ss;
    ss << date.substr(0, 4) + ' ';
    ss << date.substr(5, 2) + ' ';
    ss << date.substr(8, 2);
    ss >> y;
    ss >> m;
    ss >> d;
}
  • 判断两个 (y,m,d) 大小。
1
2
3
4
5
6
7
8
9
10
bool lessthan(int y1, int m1, int d1, int y2, int m2, int d2)
{
    if(y1 == y2)
    {
        if(m1 == m2)
            return d1 < d2;
        return m1 < m2;
    }
    return y1 < y2;
}
  • 判断闰年。
1
2
3
4
5
6
7
8
9
bool is_leap_year(int year)
{
    // 四年一闰,百年不闰,四百年再闰
    if(year % 4 != 0)
        return false;
    if(year % 100 == 0 && year % 400 != 0)
        return false;
    return true;
}
  • (y,m,d) -> 当年的第几天。
1
2
3
4
5
6
7
8
9
10
11
12
13
int day_of_year(int y, int m, int d)
{
    vector<int> months({31, -1, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31});
    if(is_leap_year(y))
        months[1] = 29;
    else
        months[1] = 28;
    int ans = 0;
    for(int i = 1; i < m; ++i)
        ans += months[i - 1];
    ans += d;
    return ans;
}

在以上组件的基础上，本题的代码如下：

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
class Solution {
public:
    int daysBetweenDates(string date1, string date2) {
        int y1, m1, d1;
        get_ymd(date1, y1, m1, d1);
        int y2, m2, d2;
        get_ymd(date2, y2, m2, d2);
        if(!lessthan(y1, m2, d1, y2, m2, d2))
        {
            swap(y1, y2);
            swap(m1, m2);
            swap(d1, d2);
        }
        int day1 = day_of_year(y1, m1, d1);
        int day2 = day_of_year(y2, m2, d2);
        if(y1 == y2)
            return day2 - day1;
        // y1 < y2
        int ans = 365 - day1;
        if(is_leap_year(y1))
            ++ans;
        ans += day2;
        for(int y = y1 + 1; y < y2; ++y)
        {
            ans += 365;
            if(is_leap_year(y))
                ++ans;
        }
        return ans;
    }
};

$3 时间

539. 最小时间差

给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

代码 (C++)

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
void get_hm(const string& s, int& h, int& m)
{
    stringstream ss;
    ss << s.substr(0, 2) + ' ';
    ss << s.substr(3);
    ss >> h;
    ss >> m;
}

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        int n = timePoints.size();
        vector<int> times(n);
        for(int i = 0; i < n; ++i)
        {
            const string &s = timePoints[i];
            int h, m;
            get_hm(s, h, m);
            times[i] = h * 60 + m;
        }

        sort(times.begin(), times.end());

        const int H = 24 * 60;
        int ans = times[0] + H - times[n - 1];
        for(int i = 0; i < n - 1; ++i)
            ans = min(ans, times[i + 1] - times[i]);
        return ans;
    }
};

681. 最近时刻

给定一个形如 “HH:MM” 表示的时刻 time ，利用当前出现过的数字构造下一个距离当前时间最近的时刻。每个出现数字都可以被无限次使用。

你可以认为给定的字符串一定是合法的。例如， “01:34” 和 “12:09” 是合法的，“1:34” 和 “12:9” 是不合法的。

代码 (C++)

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
void get_hm(const string& s, int& h, int& m)
{
    stringstream ss;
    ss << s.substr(0, 2) + ' ';
    ss << s.substr(3);
    ss >> h;
    ss >> m;
}

void get_digits(int num, unordered_set<int>& digits)
{
    if(num < 10)
        digits.insert(0);
    while(num)
    {
        digits.insert(num % 10);
        num /= 10;
    }
}

const int H = 60 * 24;

int get_dist(int start, int nxt)
{
    if(start >= nxt)
        nxt += H;
    return nxt - start;
}


class Solution {
public:
    string nextClosestTime(string time) {
        int h, m;
        get_hm(time, h, m);

        digits = unordered_set<int>();
        get_digits(h, digits);
        get_digits(m, digits);

        vector<int> cands = nxt_cands();

        int start = h * 60 + m;
        int ans = -1;
        int min_dist = H + 1;
        for(int nxt: cands)
        {
            int dist = get_dist(start, nxt);
            if(dist < min_dist)
            {
                min_dist = dist;
                ans = nxt;
            }
        }

        if(ans == -1) return "-1";
        int ans_h = ans / 60;
        string str_h = to_string(ans_h);
        if(str_h.size() == 1)
            str_h = '0' + str_h;
        int ans_m = ans % 60;
        string str_m = to_string(ans_m);
        if(str_m.size() == 1)
            str_m = '0' + str_m;
        string result = str_h + ':' + str_m;
        return result;
    }

private:
    unordered_set<int> digits;

    vector<int> nxt_cands()
    {
        vector<int> cands;
        for(int hi: digits)
            for(int hj: digits)
            {
                int h = hi * 10 + hj;
                if(h >= 24) continue;
                for(int mi: digits)
                    for(int mj: digits)
                    {
                        int m = mi * 10 + mj;
                        if(m >= 60) continue;
                        cands.push_back(h * 60 + m);
                    }
            }
        return cands;
    }
};

$4 格式转换

1507. 转变日期格式

给你一个字符串 date ，它的格式为 Day Month Year ，其中：

  • Day 是集合 {“1st”, “2nd”, “3rd”, “4th”, …, “30th”, “31st”} 中的一个元素。
  • Month 是集合 {“Jan”, “Feb”, “Mar”, “Apr”, “May”, “Jun”, “Jul”, “Aug”, “Sep”, “Oct”, “Nov”, “Dec”} 中的一个元素。
  • Year 的范围在 ​[1900, 2100] 之间。

请你将字符串转变为 YYYY-MM-DD 的格式，其中：

  • YYYY 表示 4 位的年份。
  • MM 表示 2 位的月份。
  • DD 表示 2 位的天数。

代码 (C++)

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
class Solution {
public:
    string reformatDate(string date) {
        unordered_map<string, string> month_mapping{
            {"Jan", "01"},
            {"Feb", "02"},
            {"Mar", "03"},
            {"Apr", "04"},
            {"May", "05"},
            {"Jun", "06"},
            {"Jul", "07"},
            {"Aug", "08"},
            {"Sep", "09"},
            {"Oct", "10"},
            {"Nov", "11"},
            {"Dec", "12"}
        };
        string year, month, day;
        stringstream ss;
        ss << date;
        ss >> day;
        ss >> month;
        ss >> year;
        string result;
        result.swap(year);
        result += '-';
        result += month_mapping[month];
        result += '-';
        int d;
        ss.clear();
        ss << day;
        ss >> d;
        string d_str = to_string(d);
        if(d_str.size() == 1)
            d_str = '0' + d_str;
        result+= d_str;
        return result;
    }
};

401. 二进制手表

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

  • 例如，”01:00” 是无效的时间，正确的写法应该是 “1:00” 。

分钟必须由两位数组成，可能会以零开头：

  • 例如，”10:2” 是无效的时间，正确的写法应该是 “10:02” 。

代码 (C++)

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
class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> result;
        for(int i = 0; i <= min(num, 4); ++i)
        {
            int j = num - i;
            for(int hour = 0; hour <= 11; ++hour)
            {
                if(_count1(hour) != i) continue;
                for(int minute = 0; minute <= 59; ++minute)
                {
                    if(_count1(minute) != j) continue;
                    string item_hour = to_string(hour);
                    string item_minute;
                    if(minute < 10)
                        item_minute = '0' + to_string(minute);
                    else
                        item_minute = to_string(minute);
                    result.push_back(item_hour + ':' + item_minute);
                }
            }
        }
        return result;
    }

private:
    int _count1(int n)
    {
        int result = 0;
        while(n)
        {
            ++result;
            n &= n - 1;
        }
        return result;
    }
};
Share