给你一个整数数组 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)
。
class Solution:def countCompleteDayPairs(self, hours: List[int]) -> int:k = 0 # 计数符合条件的对数n = len(hours)# 双重循环检查每对组合for i in range(n):for j in range(i):if (hours[i]+hours[j]%24 == 0): # 判断是否为24的倍数k++return k
优化
思路:
- 两数之和是24的倍数问题可以转化为一个余数相配问题。
- 我们可以通过哈希表(计数数组)来记录每个小时数除以24的余数出现的次数。
- 如果两个小时数的余数之和为24(或是0,如[0, 0]),那么它们可以配对。
优化算法:
- 维护一个大小为24的数组
remainder_count
,用来记录每个余数出现的次数。 - 遍历
hours
,对于每个小时数计算其余数,然后根据当前的已知配对策略进行统计。
举例
借鉴 1. 两数之和 的思路,遍历 hours 的同时,用一个哈希表(或者数组)记录元素的出现次数。
举几个例子:
如果 hours[i]=1,那么需要知道左边有多少个模 24 是 23 的数,这些数加上 1 都是 24 的倍数。
如果 hours[i]=2,那么需要知道左边有多少个模 24 是 22 的数,这些数加上 2 都是 24 的倍数。
如果 hours[i]=26,那么需要知道左边有多少个模 24 是 22 的数,这些数加上 26 都是 24 的倍数。
一般地,对于 hours[i],需要知道左边有多少个模 24 是 24−hours[i]mod24 的数。
特别地,如果 hours[i] 模 24 是 0,那么需要知道左边有多少个模 24 也是 0 的数。
这两种情况可以合并为:累加左边(24−hours[i]mod24)mod24的出现次数。
代码实现时,用一个长为 24 的数组 cnt 维护 hours[i]mod24 的出现次数。
from typing import Listclass Solution:def countCompleteDayPairs(self, hours: List[int]) -> int:remainder_count = [0] * 24 # 记录每个余数的出现次数pairs = 0 # 记录有效配对的数量# 遍历每个小时数for hour in hours:remainder = hour % 24 # 计算余数complement = (24 - remainder) % 24 # 找到配对所需的余数# 如果已经有配对的余数,增加配对数量pairs += remainder_count[complement]# 更新当前余数的计数remainder_count[remainder] += 1return pairs
参考:灵茶山艾府--https://leetcode.cn/problems/count-pairs-that-form-a-complete-day-ii/solutions/2812385/tao-lu-mei-ju-you-wei-hu-zuo-pythonjavac-3vhv/