KK's blog

LeetCode 071 Simplify Path

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

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

The path starts with a single slash '/'. Any two directories are separated by a single slash '/'.
The path does not end with a trailing '/'. The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

Input: path = “/home/“
Output: “/home”
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: path = “/../“
Output: “/“
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: path = “/home//foo/“
Output: “/home/foo”
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Constraints:

1 <= path.length <= 3000 path consists of English letters, digits, period '.', slash '/' or '_'.
* path is a valid absolute Unix path.

题目大意：

简化路径，遇.表示当前目录不做事，遇..表示到上一个目录

解题思路：

路径类似于括号题，利用括号题模板

解题步骤：

N/A

注意事项：

edge case /../ 表示若stack为空，就不pop。if stack不能加到elif token == ‘..’中
遇到..返回到上层目录

Python代码：

def simplifyPath(self, path: str) -> str:
	path += '/'
	token, stack = '', []
	for c in path:
		if c == '/':
			if token == '.':
				pass
			elif token == '..':
				if stack: # remember
					stack.pop()
			elif token:
				stack.append(token)
			token = ''
		else:
			token += c
	return '/' + '/'.join(stack)

算法分析：

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

LeetCode 1010 Pairs of Songs With Total Durations Divisible by 60

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

LeetCode

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)