【LeetCode】每日一题 2024_10_22 构成整天的下标对数目 I(暴力/哈希)
前言
每天和你一起刷 LeetCode 每日一题~
LeetCode 启动!
题目:构成整天的下标对数目 I
今天刷题的时候看了一眼明天的每日一题:构成整天的下标对数目 II,和这道题一模一样,只是数据范围增强了,所以这次题解把优化情况写完之后,明天可能就不重复更新了~
代码与解题思路
依照惯例,如果可以暴力那就先暴力解一解,题目要求找到两个元素和%24 == 0 的情况有多少种,那我们只需要两层循环遍历所有情况然后计数即可:
func countCompleteDayPairs(hours []int) (ans int) {
for i, v := range hours {
for j := i+1; j < len(hours); j++ {
if (v+hours[j])%24 == 0 {
ans++
}
}
}
return ans
}
假设题目数据范围不允许暴力,怎么用 O(N) 的解法做这道题?
今天这道题其实和力扣经典题目两数之和非常像,举个例子:
第一个数选了 1,第二个数要选什么才能让两数之和 % 24 == 0?
很明显需要选 % 24 == 23 的数,比如说 23,47 等等
第一个数选了 2,第二个数就得选 % 24 == 22 的数 . . . 以此类推
换句话说,当我们枚举第一个数的时候,只需要知道有多少个能与他匹配 % 24 == 0 的数即可:
func countCompleteDayPairs(hours []int) (ans int) {
mp := map[int]int{}
for _, v := range hours {
ans += mp[(24-v%24)%24]
mp[v%24]++
}
return ans
}
我们记录 v % 24 出现的次数,而与他匹配的元素就是 24 - v % 24,让 ans 直接增加能够匹配的数量即可
补充:为什么这里 (24-v%24)%24 在最后还需要 % 24?
答:当第一个数选了 0/24/48 这种 % 24 == 0 的情况,第二个数我们就需要选择 % 24 == 0 值,而这种情况下的 24 - v % 24 == 24,对他再 % 24 就能特判 == 24 的情况,让这种情况的结果变成 0,而其他情况不受影响
每天进步一点点,我们明天不见不散~
可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。