Daily classic

Looking at Tianmen Mountain — Li Bai (Tang dynasty)

Tianmen interrupted Chu River open, clear water east flow so far back.

The green hills on both sides were opposite each other, and the lone sail came to the edge of the sun.

describe

You are given a list of songs where the ith 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 such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: time = [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
Copy the code

Example 2:

Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Copy the code

Note:

1 <= time.length <= 6 * 10^4
1 <= time[i] <= 500
Copy the code

parsing

Give a list of songs where the duration of song I is time[I] seconds. Returns the number of song pairs whose total duration in seconds is divisible by 60. Formally, we want the number of indexes I and j such that I < j and (time[I] + time[j]) % 60 == 0.

The time array is very long, so the time complexity of the violent solution is O(n^2), but the code here is for reference. Time [I] + time[j] == 60 or time[I] + time[j] == 0 Return result at the end of the loop, which is simple, but will not pass.

answer

class Solution(object):
    def numPairsDivisibleBy60(self, time):
        """
        :type time: List[int]
        :rtype: int
        """
        for i,t in enumerate(time):
            time[i] = t%60
        result = 0
        for i,t in enumerate(time):
            for j in range(i+1,len(time)):
                if time[i] + time[j] == 60 or time[i] + time[j] == 0:
                    result += 1
        return result
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

In fact, the timeout above is because of the two-layer loop, we can improve on the above, simplify to one layer loop, so the time is down to O(n), but we need to use the dictionary to do some preliminary calculations. When modulating time, a statistic of the result of modulating time is also made and stored in dictionary D, for example: Time = [30,20,150,100,40,60,60], time = [30,20,30,40,40,0,0], calculation result d = {30:2, 20:1, 40:2, 0:2}.

  • D [t] * (d[t] -1) // 2 add to result if time t == 30 or t == 0 The same calculation is performed for songs whose modulus is 0;

  • Otherwise, if 60-t is in the dictionary, d[t] * d[60-t] can be added to result. Meanwhile, in order to avoid double calculation, set d[t] and d[60-t] to 0, such as traversing the song whose modulus is 20. For sure, it can be combined with songs whose modulus is 40, and the total number is D [20] * D [40]. However, at this time, the combinable pairs of two songs have been calculated into the result, so the values are set to 0 to avoid repeated addition of song pairs when traversing songs whose modulus is 40.

  • After iterating through the dictionary, return result.

In fact, in general, what we find is that sometimes the algorithm just needs to do some optimization on the basis of the brute force algorithm to pass.

answer

class Solution(object):
    def numPairsDivisibleBy60(self, time):
        """
        :type time: List[int]
        :rtype: int
        """
        d = {}
        result = 0
        for i, t in enumerate(time):
            t = t % 60
            if t not in d:
                d[t] = 1
            else:
                d[t] += 1
            time[i] = t
        for i, t in enumerate(d):
            if t == 30 or t == 0:
                c = d[t]
                result += c * (c - 1) // 2
            elif 60-t in d:
                result += (d[t] * d[60 - t])
                d[t] = 0
                d[60 - t] = 0
        return result
        	      
		
Copy the code

The results

Runtime: 192 ms, Faster than 73.42% of Python online submissions for Songs With Total Durations Divisible by 60. Memory Usage: Submissions for Python online submissions With Total Durations Divisible by 60.Copy the code

Original link: leetcode.com/problems/pa…

Your support is my biggest motivation