给你一个整数数组 hours,表示以 小时 为单位的时间,返回一个整数,表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如,1 天是 24 小时,2 天是 48 小时,3 天是 72 小时,以此类推。
示例 1:
输入: hours = [12,12,30,24,24]
输出: 2
解释:
构成整天的下标对分别是 (0, 1) 和 (3, 4)。
示例 2:
输入: hours = [72,48,24,3]
输出: 3
解释:
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。
提示:
1 <= hours.length <= 5 * 105
1 <= hours[i] <= 109
解题思路:
上篇我们已经使用暴力求解的方式得到答案了,今天这题难度升级,暴力解是行不通的,题目要求是24 小时的 整数倍,那么无论任何一个数对24取余就只有0-23的值
这样我们就缩小了范围,再根据取余的结果相加能除以24的就能得到最终的结果
完整代码:/*** 计算完整的白天和黑夜对数* 此方法旨在找出在给定的一组小时中,哪些小时可以组成完整的24小时周期* 这对于分析如工作班次、活动周期等问题可能很有用* 其中 ans += cnt[(24 - hour % 24) % 24];cnt[hour % 24]++;这两场代码做下特殊解释分步解析1.计算 hour % 24:hour % 24:取当前小时 hour 对 24 取模,确保 hour 在 0 到 23 之间。例如,如果 hour 是 25,那么 25 % 24 等于 1。2.计算 (24 - hour % 24) % 24:(24 - hour % 24) % 24:计算与当前小时 hour 组成完整一天的另一个小时。例如,如果 hour 是 1,那么 (24 - 1) % 24 等于 23;如果 hour 是 23,那么 (24 - 23) % 24 等于 1。这个表达式的作用是找到与当前小时 hour 相加等于 24 的另一个小时。例如,如果 hour 是 1,那么需要找到 23 小时才能组成 24 小时。3.访问 cnt 数组:cnt[(24 - hour % 24) % 24]:访问 cnt 数组中对应位置的值。这个值表示之前已经遍历过的小时中,有多少个小时与当前小时 hour 组成完整一天。例如,如果 hour 是 1,那么 cnt[23] 表示之前已经遍历过的小时中有多少个 23 小时。4.累加到 ans:ans += cnt[(24 - hour % 24) % 24]:将 cnt 数组中对应位置的值累加到 ans 中。这表示当前小时 hour 与之前已经遍历过的小时能组成完整一天的对数* @param hours 代表不同时间段的小时数组* @return 返回组成完整24小时周期的小时对数*/public long countCompleteDayPairs(int[] hours) {// 初始化答案变量,用于累计完整的24小时周期对数long ans = 0;// 创建一个长度为24的数组,用于记录每个小时出现的次数int[] cnt = new int[24];// 遍历输入的小时数组for (int hour : hours) {// 计算当前小时与哪个小时可以组成完整的24小时,并累加到答案中// 这里使用模运算来处理跨夜的情况,确保计算结果在0到23之间ans += cnt[(24 - hour % 24) % 24];// 记录当前小时出现的次数cnt[hour % 24]++;}// 返回累计的完整24小时周期对数return ans;}示例:假设 hours 数组为 [1, 23, 23, 1, 23],我们来逐步分析:1.初始状态:ans = 0cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]2.遍历第一个小时 1:hour = 1ans += cnt[(24 - 1) % 24] 即 ans += cnt[23],此时 cnt[23] 为 0,所以 ans 仍为 0。cnt[1]++,cnt 变为 [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]3.遍历第二个小时 23:hour = 23ans += cnt[(24 - 23) % 24] 即 ans += cnt[1],此时 cnt[1] 为 1,所以 ans 变为 1。cnt[23]++,cnt 变为 [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]4.遍历第三个小时 23:hour = 23ans += cnt[(24 - 23) % 24] 即 ans += cnt[1],此时 cnt[1] 为 1,所以 ans 变为 2。cnt[23]++,cnt 变为 [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0]5.遍历第四个小时 1:hour = 1ans += cnt[(24 - 1) % 24] 即 ans += cnt[23],此时 cnt[23] 为 2,所以 ans 变为 4。cnt[1]++,cnt 变为 [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0]6.遍历第五个小时 23:hour = 23ans += cnt[(24 - 23) % 24] 即 ans += cnt[1],此时 cnt[1] 为 2,所以 ans 变为 6。cnt[23]++,cnt 变为 [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0]最终,ans 的值为 6,表示有 6 对小时能组成完整的一天