题目描述
给你一个整数数组 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)
。
解题思路
使用一个长度为24的mod数组存储hours余24的余数,记录余数为0-23的个数,其中余数为0的数本身就是24的倍数,是可以直接凑成整天的,只需要从余数为零的总个数(假设为n)中使用排列数取出两个就能组成一对,即Cn2。对于剩下的数据,余数为1的可以和余数为23的凑成一对,余数为2的可以和余数为22的凑成一对,以此类推,可以计算出所有的个数。注意数据范围,否则会爆RE。
AC代码
标签:24,10,12,23,hours,long,2024,余数,mod From: https://blog.csdn.net/qq_51019596/article/details/143177172class Solution {
public:
long long countCompleteDayPairs(vector<int>& hours) {
long long ans = 0;
long long mod[24];
memset(mod, 0, sizeof mod);
for(auto x: hours)
mod[x % 24] ++;
for(int i = 1; i < 24, i != 12; i ++)
ans += mod[i] * mod[24 - i];
ans += mod[0] * (mod[0] - 1) / 2;
ans += mod[12] * (mod[12] - 1) / 2;
return ans;
}
};