Easy

题目描述

编写一个程序，计算两个日期之间的天数。

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

示例 1：

输入：date1 = "2019-06-29", date2 = "2019-06-30"
输出：1

示例 2：

输入：date1 = "2020-01-15", date2 = "2019-12-31"
输出：15

约束：

  • 给定的日期是 1971 年到 2100 年之间的有效日期。

提示：

  • 创建一个函数 f(date)，计算从 1900-01-01 到 date 的天数。我们如何计算答案？
  • 答案就是 |f(date1) - f(date2)|。
  • 如何构造 f(date)？
  • 对于从 1900 年到 year - 1 年的每一年，累加 365 天或闰年的 366 天。然后对每个月累加天数，考虑当前年份是闰年的情况，最后累加天数。

解题思路

这道题要求计算两个日期之间的天数差，根据题目提示，我们可以采用"基准日期"的思路来解决。

解题思路

核心思想是将每个日期转换为从某个固定基准日期（如 1900-01-01）开始的天数，然后计算两个天数的差值的绝对值。

具体步骤：

  1. 解析日期字符串：提取年、月、日信息
  2. 计算从基准日期的天数：
    • 累加从基准年到目标年前一年的所有天数（考虑闰年）
    • 累加目标年中从1月到目标月前一月的所有天数
    • 加上目标月中的天数
  3. 判断闰年：能被4整除但不能被100整除，或者能被400整除
  4. 计算差值：取两个日期天数的绝对值差

这种方法的优势在于将复杂的日期计算转化为简单的数值运算，避免了直接处理跨年、跨月等复杂情况。时间复杂度主要取决于年份跨度，在给定约束下是常数级别的。

另一种思路是使用编程语言内置的日期库，但手动实现更能体现算法思维。

代码实现

class Solution {
public:
    int daysBetweenDates(string date1, string date2) {
        return abs(daysSince1900(date1) - daysSince1900(date2));
    }
    
private:
    bool isLeapYear(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }
    
    int daysSince1900(string date) {
        int year = stoi(date.substr(0, 4));
        int month = stoi(date.substr(5, 2));
        int day = stoi(date.substr(8, 2));
        
        int days = 0;
        
        // 累加从1900年到year-1年的天数
        for (int y = 1900; y < year; y++) {
            days += isLeapYear(y) ? 366 : 365;
        }
        
        // 每月天数
        vector<int> monthDays = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if (isLeapYear(year)) {
            monthDays[1] = 29;
        }
        
        // 累加目标年中1月到month-1月的天数
        for (int m = 0; m < month - 1; m++) {
            days += monthDays[m];
        }
        
        // 加上目标月中的天数
        days += day;
        
        return days;
    }
};

class Solution:
    def daysBetweenDates(self, date1: str, date2: str) -> int:
        def is_leap_year(year):
            return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)
        
        def days_since_1900(date):
            year, month, day = map(int, date.split('-'))
            days = 0
            
            # 累加从1900年到year-1年的天数
            for y in range(1900, year):
                days += 366 if is_leap_year(y) else 365
            
            # 每月天数
            month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
            if is_leap_year(year):
                month_days[1] = 29
            
            # 累加目标年中1月到month-1月的天数
            for m in range(month - 1):
                days += month_days[m]
            
            # 加上目标月中的天数
            days += day
            
            return days
        
        return abs(days_since_1900(date1) - days_since_1900(date2))

public class Solution {
    public int DaysBetweenDates(string date1, string date2) {
        return Math.Abs(DaysSince1900(date1) - DaysSince1900(date2));
    }
    
    private bool IsLeapYear(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }
    
    private int DaysSince1900(string date) {
        string[] parts = date.Split('-');
        int year = int.Parse(parts[0]);
        int month = int.Parse(parts[1]);
        int day = int.Parse(parts[2]);
        
        int days = 0;
        
        // 累加从1900年到year-1年的天数
        for (int y = 1900; y < year; y++) {
            days += IsLeapYear(y) ? 366 : 365;
        }
        
        // 每月天数
        int[] monthDays = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if (IsLeapYear(year)) {
            monthDays[1] = 29;
        }
        
        // 累加目标年中1月到month-1月的天数
        for (int m = 0; m < month - 1; m++) {
            days += monthDays[m];
        }
        
        // 加上目标月中的天数
        days += day;
        
        return days;
    }
}

/**
 * @param {string} date1
 * @param {string} date2
 * @return {number}
 */
var daysBetweenDates = function(date1, date2) {
    const d1 = new Date(date1);
    const d2 = new Date(date2);
    return Math.abs((d2 - d1) / (1000 * 60 * 60 * 24));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)由于年份范围限定在1971-2100年，最多迭代200年，是常数级别
空间复杂度O(1)只使用了常数级别的额外空间存储变量

相关题目