【每日一题Day180】LC2409统计共同度过的日子数 | 模拟

统计共同度过的日子数【LC2409】

Alice 和 Bob 计划分别去罗马开会。

给你四个字符串 arriveAlice ，leaveAlice ，arriveBob 和 leaveBob 。Alice 会在日期 arriveAlice 到 leaveAlice 之间在城市里（日期为闭区间），而 Bob 在日期 arriveBob 到 leaveBob 之间在城市里（日期为闭区间）。每个字符串都包含 5 个字符，格式为 "MM-DD" ，对应着一个日期的月和日。

请你返回 Alice和 Bob 同时在罗马的天数。

你可以假设所有日期都在 同一个 自然年，而且 不是 闰年。每个月份的天数分别为：[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 。

继续看看昨天的线段树了

• 思路：

  将每个日期转化为一年中的第几天，然后判断有无交集，如果有则返回相交的天数

• 实现

  • 使用前缀和数组计算每个月对应的天数

  class Solution {public int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int[] sum = new int[13];for (int i = 0; i < 12; i++){sum[i + 1] = sum[i] + days[i];}int aArriveDay = sum[Integer.valueOf(arriveAlice.substring(0,2)) - 1] + Integer.valueOf(arriveAlice.substring(3,5));int aLeaveDay = sum[Integer.valueOf(leaveAlice.substring(0,2)) - 1] + Integer.valueOf(leaveAlice.substring(3,5));int bArriveDay = sum[Integer.valueOf(arriveBob.substring(0,2)) - 1] + Integer.valueOf(arriveBob.substring(3,5));int bLeaveDay = sum[Integer.valueOf(leaveBob.substring(0,2)) - 1] + Integer.valueOf(leaveBob.substring(3,5));if (aLeaveDay < bArriveDay || bLeaveDay < aArriveDay){// 没有相交区域return 0;}return Math.min(aLeaveDay, bLeaveDay) - Math.max(aArriveDay, bArriveDay) + 1;}
  }
  

  • 复杂度
    • 时间复杂度：$O(C)$，本题中C为12
    • 空间复杂度：$O(C)$