2025-01-17:构成整天的下标对数目Ⅰ。用go语言,给定一个整数数组 hours,其中每个元素表示以小时为单位的时间,要求返回一个整数,表示满足条件 i < j 且 hours[i] + hours[j] 为 24 的整数倍的下标对 (i, j) 的数量。
这里,整天被定义为时间持续的时长是 24 小时的整数倍。例如,1天为24小时,2天为48小时,3天为72小时,以此类推。
1 <= hours.length <= 100。
1 <= hours[i] <= 1000000000。
输入: hours = [12,12,30,24,24]。
输出: 2。
解释:
构成整天的下标对分别是 (0, 1) 和 (3, 4)。
答案2025-01-17:
题目来自leetcode3184。
大体步骤如下:
力扣上的官方题解用的是暴力法,并不是最优解。
1.首先,创建一个长度为 24 的数组 m
,用于记录每个小时数模 24 的次数。
2.将第一个小时数小时数模 24 的出现次数加一,即 m[hours[0]%24]++
。
3.初始化变量 ans
为 0,用于记录符合条件的下标对数目。
4.从数组的第二个元素开始遍历,对于每个小时数计算其小时数模 24 的值 hi
。
5.计算相补数 he
,即 he = (24 - hi) % 24
,用于检查是否存在和当前小时数相补的小时数构成完整天。
6.如果 m[he]
大于 0,说明存在和当前小时数相补的小时数,将符合条件的组合数累加到 ans
中。
7.最后,更新记录当前小时数模 24 的次数,即 m[hi]++
。
8.返回 ans
,即可得到符合条件的下标对数量。
总的时间复杂度为 O(n),其中 n 为 hours
数组的长度,因为需要遍历整个数组一次。
总的额外空间复杂度为 O(1),因为所需的额外空间是固定大小的数组大小与常数变量。
Go完整代码如下:
package main
import (
"fmt"
)
func countCompleteDayPairs(hours []int) int {
var m [24]int
m[hours[0]%24]++
var ans int
for i := 1; i < len(hours); i++ {
hi := hours[i] % 24
he := (24 - hi) % 24
if m[he] > 0 {
ans += m[he]
}
m[hi]++
}
return ans
}
func main() {
hours := []int{72, 48, 24, 3}
result := countCompleteDayPairs(hours)
fmt.Println(result)
}
Rust完整代码如下:
fn count_complete_day_pairs(hours: Vec<i32>) -> i32 {
let mut m = vec![0; 24];
m[(hours[0] % 24) as usize] += 1;
let mut ans = 0;
for i in 1..hours.len() {
let hi = (hours[i] % 24) as usize;
let he = (24 - hi as i32) % 24;
if m[he as usize] > 0 {
ans += m[he as usize];
}
m[hi] += 1;
}
ans
}
fn main() {
let hours = vec![72, 48, 24, 3];
let result = count_complete_day_pairs(hours);
println!("{}", result);
}
C完整代码如下:
#include <stdio.h>
int countCompleteDayPairs(int hours[], int size) {
int m[24] = {0}; // 初始化一个长度为 24 的数组
m[hours[0] % 24]++;
int ans = 0;
for (int i = 1; i < size; i++) {
int hi = hours[i] % 24;
int he = (24 - hi) % 24;
if (m[he] > 0) {
ans += m[he];
}
m[hi]++;
}
return ans;
}
int main() {
int hours[] = {72, 48, 24, 3};
int size = sizeof(hours) / sizeof(hours[0]); // 计算数组大小
int result = countCompleteDayPairs(hours, size);
printf("%d\n", result);
return 0;
}
C++完整代码如下:
#include <iostream>
#include <vector>
int countCompleteDayPairs(const std::vector<int>& hours) {
std::vector<int> m(24, 0); // 初始化一个大小为 24 的向量,初始值为 0
m[hours[0] % 24]++;
int ans = 0;
for (size_t i = 1; i < hours.size(); ++i) {
int hi = hours[i] % 24;
int he = (24 - hi + 24) % 24; // 确保 he 为非负
ans += m[he]; // 增加与 he 相关的计数
m[hi]++; // 更新小时 hi 的计数
}
return ans;
}
int main() {
std::vector<int> hours = {72, 48, 24, 3};
int result = countCompleteDayPairs(hours);
std::cout << result << std::endl; // 输出结果
return 0;
}
Python完整代码如下:
# -*-coding:utf-8-*-
def count_complete_day_pairs(hours):
m = [0] * 24 # 初始化一个大小为 24 的列表
m[hours[0] % 24] += 1
ans = 0
for i in range(1, len(hours)):
hi = hours[i] % 24
he = (24 - hi) % 24
if m[he] > 0:
ans += m[he]
m[hi] += 1
return ans
if __name__ == "__main__":
hours = [72, 48, 24, 3]
result = count_complete_day_pairs(hours)
print(result) # 输出结果
Javascript完整代码如下:
function countCompleteDayPairs(hours) {
const m = new Array(24).fill(0); // 初始化一个大小为 24 的数组
m[hours[0] % 24]++;
let ans = 0;
for (let i = 1; i < hours.length; i++) {
const hi = hours[i] % 24;
const he = (24 - hi) % 24;
if (m[he] > 0) {
ans += m[he];
}
m[hi]++;
}
return ans;
}
const hours = [72, 48, 24, 3];
const result = countCompleteDayPairs(hours);
console.log(result); // 输出结果
Solidity完整代码如下:
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract DayPairCounter {
function countCompleteDayPairs(uint[] memory hours2) public pure returns (uint) {
uint[24] memory occurrences;
occurrences[hours2[0] % 24]++;
uint ans;
for (uint i = 1; i < hours2.length; i++) {
uint hi = hours2[i] % 24;
uint he = (24 - hi) % 24;
if (occurrences[he] > 0) {
ans += occurrences[he];
}
occurrences[hi]++;
}
return ans;
}
function testCountCompleteDayPairs() public pure returns (uint) {
uint[] memory hours2 = new uint[](4);
hours2[0] = 72;
hours2[1] = 48;
hours2[2] = 24;
hours2[3] = 3;
return countCompleteDayPairs(hours2);
}
}
标签:24,int,整数,hours,hi,ans,go,he
From: https://blog.csdn.net/weixin_48502062/article/details/145205284