Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit028bdbf

Browse files
1010 Pairs of Songs With Total Durations Divisible by 60.py
1 parenta6cecc7 commit028bdbf

File tree

1 file changed

+65
-0
lines changed

1 file changed

+65
-0
lines changed
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
#!/usr/bin/python3
2+
"""
3+
In a list of songs, the i-th song has a duration of time[i] seconds.
4+
5+
Return the number of pairs of songs for which their total duration in seconds is
6+
divisible by 60. Formally, we want the number of indices i < j with (time[i] +
7+
time[j]) % 60 == 0.
8+
9+
Example 1:
10+
11+
Input: [30,20,150,100,40]
12+
Output: 3
13+
Explanation: Three pairs have a total duration divisible by 60:
14+
(time[0] = 30, time[2] = 150): total duration 180
15+
(time[1] = 20, time[3] = 100): total duration 120
16+
(time[1] = 20, time[4] = 40): total duration 60
17+
Example 2:
18+
19+
Input: [60,60,60]
20+
Output: 3
21+
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
22+
23+
Note:
24+
1 <= time.length <= 60000
25+
1 <= time[i] <= 500
26+
"""
27+
fromtypingimportList
28+
fromcollectionsimportdefaultdict
29+
30+
31+
classSolution:
32+
defnumPairsDivisibleBy60(self,time:List[int])->int:
33+
"""
34+
Running attribution
35+
"""
36+
counter=defaultdict(int)
37+
ret=0
38+
fortintime:
39+
ret+=counter[(60-t)%60]# handle 0
40+
counter[t%60]+=1
41+
42+
returnret
43+
44+
45+
defnumPairsDivisibleBy60_error(self,time:List[int])->int:
46+
"""
47+
O(N^2) check i, j
48+
Reduce it
49+
O(N) by using hashmap, the key should mod 60
50+
51+
attribution error
52+
"""
53+
hm=defaultdict(int)
54+
fortintime:
55+
hm[t%60]+=1
56+
57+
ret=0
58+
fork,vinhm.items():
59+
ifk==0:
60+
ret+= (v* (v-1))//2
61+
elifk<=60-k:# attribution
62+
v2=hm[60-k]
63+
ret+=v2*v
64+
65+
returnret

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp