Pairs of Songs With Total Durations Divisible by 60 LT1010
2024-10-21 06:20:46
In a list of songs, the i-th song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Example 2:
Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Idea 1. Similar to Two Sum LT1, map with modular arithmetic
class Solution {
public int numPairsDivisibleBy60(int[] time) {
Map<Integer, Integer> record = new HashMap<>();
int count = 0;
for(int val: time) {
val = val%60;
count += record.getOrDefault((60 - val)%60, 0);
record.put(val, record.getOrDefault(val, 0) + 1);
}
return count;
}
}
array used as map
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] record = new int[60];
int count = 0;
for(int val: time) {
val = val%60;
count += record[(60 - val)%60];
++record[val];
}
return count;
}
}
Idea 1a. count pairs, preprose the array first
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] record = new int[60];
for(int val: time) {
val = val%60;
++record[val];
}
int count = 0;
if(record[0] > 0) {
count += record[0] * (record[0]-1)/2;
}
if(record[30] > 0) {
count += record[30] * (record[30]-1)/2;
}
for(int i = 1; i < 30; ++i) {
count += record[i]*record[60-i];
}
return count;
}
}
Note:
1 <= time.length <= 600001 <= time[i] <= 500
最新文章
- Struts2的经典入门
- Oralce 账户被锁后的解决办法
- jmeter的压力测试
- ABAP ALV单个单元格状态编辑-简单版本
- java产生随机数并求和
- VS2005打开VS2008 VS2010 VS2012
- Hibernate应用SQL查询返回实体类型
- Hive学习之五 《Hive进阶—UDF操作案例》 详解
- 【转】中断处理函数中不用disable_irq而用disable_irq_nosync原因
- 转：一个跨WINDOWS LINUX平台的线程类
- 第二章：2.8 通过Django 在web页面上面输出 “Hello word ”
- Linux(CentOS6.5)下修改Nginx初始化配置
- docker结合jenkins、gitlab实现.netcore的持续集成实践
- PHP单元测试使用
- Mac 下 Homebrew（类似CentOS下的yum）简介及安装
- AD采样的一个例子
- 127. Word Ladder（单词变换 广度优先）
- JavaWeb学习笔记（十七）—— 数据库连接池
- WPF数据视图学习
- 你所不知道的，Java 中操作符的秘密？