KK's blog

LeetCode 1010 Pairs of Songs With Total Durations Divisible by 60

Posted on 2021-12-26 Edited on 2026-06-03 Disqus:

You are given a list of songs where 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 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

Example 2:

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

Constraints:

`1 <= time.length <= 6 10⁴*1 <= time[i] <= 500`

题目大意：

求数组中两数和能被60整除

解题思路：

两数和的关系第一时间想到two sum。但由于target是60的倍数，并不固定，所以先用公式求所有数的mod，(time[i] + time[j]) % 60 = time[i] % 60 + time[j] % 60, 这样target就是60了
第二个难点是此题求个数并不是像two sum一样求可行性，所以value to index改成value to count

解题步骤：

N/A

注意事项：

对所有数对60求mod，map存value到count
如果输入是60，取模后为0， 求(60 - time_mod[i])要对60取模，否则60不在map中，因为60 - time_mod[i] = 60.

Python代码：

# (time[i] + time[j]) % 60 = time[i] % 60 + time[j] % 60
def numPairsDivisibleBy60(self, time: List[int]) -> int:
	time_mod = [t % 60 for t in time] # [30,30]
	val_to_count = collections.defaultdict(int)
	res = 0
	for i in range(len(time_mod)):
		if (60 - time_mod[i]) % 60 in val_to_count:
		   res += val_to_count[(60 - time_mod[i]) % 60]
		val_to_count[time_mod[i]] += 1 # 30:1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode 526 Beautiful Arrangement

Posted on 2021-12-26 Edited on 2026-06-03 Disqus:

LeetCode

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

perm[i] is divisible by i. i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

Example 2:

Input: n = 1
Output: 1

Constraints:

* 1 <= n <= 15

题目大意：

求数组中所有排列中下标（从1开始）和数值能整除（下标整除数值或反之）的个数

解题思路：

一开始考虑用DP，因为求个数且类似于L368 Largest Divisible Subset，但问题与子问题的具体排位有关，所以DP不可行。考虑用Stack，但数组顺序可变。
只能用暴力法，也就是DFS中排列求解

解题步骤：

N/A

注意事项：

用排列模板，但此题不涉及具体数组。用set来记录访问过的数值而不是下标，start来记录模拟结果path中的位置

Python代码：

def countArrangement(self, n: int) -> int:
	return self.permute(n, 1, set())

def permute(self, n, start, visited): # 2, 1, [F,F,F]
	if start == n + 1: # remember n + 1
		#print(path)
		return 1
	res = 0 # 1
	for i in range(1, n + 1): # [1,3)
		if i in visited:
			continue
		if i % start == 0 or start % i == 0:
			visited.add(i)
			#path.append(i)
			res += self.permute(n, start + 1, visited) # 2, 2, [FFT]
			#path.pop()
			visited.remove(i)
	return res

算法分析：

时间复杂度为O(解大小)，空间复杂度O(n)

LeetCode 759 Employee Free Time

Posted on 2021-12-26 Edited on 2026-06-03 Disqus:

LeetCode

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren’t finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints:

1 <= schedule.length , schedule[i].length <= 50 0 <= schedule[i].start < schedule[i].end <= 10^8

题目大意：

给定员工的schedule，给所有员工的空余时间的区间

解题思路：

一开始考虑用Leetcode 056 merge intervals，然后求不能merge时的区间。后来想用Leetcode 253 meeting rooms II也是关于重合区间，只要active meetings为0时，就表示空余区间，此法更容易实现

解题步骤：

N/A

注意事项：

用Leetcode 253 meeting rooms II的排序解法
注意输入是每一个员工的schedule如[Interval(1, 2), Interval(5, 6)]，然后是所有员工schedule的列表

Python代码：

def test(self):
	TestCases.compare(self, self.employeeFreeTime([[Interval(1, 2), Interval(5, 6)], [Interval(1, 3)], [Interval(4, 10)]]), [Interval(3, 4)])

def employeeFreeTime(self, schedule: [[Interval]]) -> [Interval]:
	schedule_endpoints = []
	for li in schedule:
		for s in li:
			schedule_endpoints.append((s.start, 0)) # [(1, 0),(2,1),(5,0), (6,1)]
			schedule_endpoints.append((s.end, 1))
	schedule_endpoints.sort()
	res, free_time, active_schedule = [], [], 0
	for i in range(len(schedule_endpoints)):
		if schedule_endpoints[i][1] == 0:
			active_schedule += 1 # 0
		else:
			active_schedule -= 1 #
		if active_schedule == 0:
			free_time.append(schedule_endpoints[i][0]) #[2,5]
		if active_schedule == 1 and len(free_time) == 1:
			free_time.append(schedule_endpoints[i][0])
			free_interval = Interval(free_time[0], free_time[1])
			res.append(free_interval)
			free_time = []
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)

LeetCode 907 Sum of Subarray Minimums

Posted on 2021-12-26 Edited on 2026-06-03 Disqus:

LeetCode

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10⁹ + 7.

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

Constraints:

1 <= arr.length <= 3 10⁴

1 <= arr[i] <= 3 10⁴

题目大意：

求所有子数组的最小值的和

算法思路：

求区间最值用Stack，因为是最小值，所以用递增栈
一开始考虑用类似DP，因为若知道[3, 2, 6]栈为[2, 6], 8入栈，8与每一个栈内元素计算最小值，优化是用栈内的累计和，如2和6对应的累计和而不用每个元素计算。
参考了网上算法，栈内每个元素向左向右区间内（包括自己）均是最小值，所以出栈时候进行计算即可。
如[3, 2, 8, 7, 6, 9, 10, 4]栈是[2, 6, 9, 10]对应的下标，现在4入栈，9和10出栈后，6准备出栈。
prev_idx为6的下标4， i是7，6是[8, 7, 6], [7, 6], [6]三个区间的最小值prev_idx - stack[-1] = 3个区间，
而这些区间的最小值的和还要再乘以后面的大于它的数，如[7, 6]这个区间可以和这些区间合并[7, 6], [7, 6, 9], [7, 6, 9, 10], 所以(i - prev_idx) = 3
这就是arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)的精髓

注意事项：

头尾加入最小值，加入头部因为公式需要栈内的前元素，这样可以处理只有一个元素出栈的情况。尾部加入最小值因为确保所有元素都出栈。

Python代码：

def sumSubarrayMins(self, arr: List[int]) -> int:
	arr.insert(0, -sys.maxsize)
	arr.append(-sys.maxsize)
	stack, res = [], 0
	for i in range(len(arr)):
		while stack and arr[i] < arr[stack[-1]]:
			prev_idx = stack.pop()
			res += arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
			res = res % (pow(10, 9) + 7)
		stack.append(i)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode 2121 Intervals Between Identical Elements

Posted on 2021-12-25 Edited on 2026-06-03 Disqus:

LeetCode

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

Constraints:

n == arr.length 1 <= n <= 10<sup>5</sup>
* 1 <= arr[i] <= 10<sup>5</sup>

题目大意：

求相同元素的下标差的和

解题思路：

暴力法是TLE，由于存在重复计算。用prefix和suffix来优化。
prefix为从某个元素为起点到前继节点下标差之和
suffix为从某个元素为起点到后继节点下标差之和
结果 = prefix[i] + suffix[i]

解题步骤：

用Map来存储相同元素的下标
用prefix和suffix来计算每个元素的结果

注意事项：

一开始用presum表示从起点到其他下标的差之和。这不能用于某个元素的前继元素下标差之和。所以要改成从某个元素为起点到前继节点下标差之和

Python代码：

def getDistances(self, arr: List[int]) -> List[int]:
	val_to_index = collections.defaultdict(list)
	res = [0] * len(arr)
	for i in range(len(arr)):
		val_to_index[arr[i]].append(i)
	for val, indices in val_to_index.items():
		prefix, suffix = [0], [0]
		for i in range(1, len(indices)):
			prefix.append(prefix[-1] + i * abs(indices[i] - indices[i - 1]))
		for i in range(len(indices) - 2, -1, -1):
			suffix.append(suffix[-1] + (len(indices) - i - 1) * abs(indices[i] - indices[i + 1]))
		for i in range(len(indices)):
			res[indices[i]] = prefix[i] + suffix[len(indices) - i - 1]
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)