KK's blog

LeetCode 526 Beautiful Arrangement

Posted on 2021-12-26 Disqus:

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 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 1010 Pairs of Songs With Total Durations Divisible by 60

Posted on 2021-12-26 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 018 4Sum

Posted on 2021-12-26 Edited on 2021-12-27 Disqus:

LeetCode

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints: 1 <= nums.length <= 200
-109 <= nums[i] <= 109 -109 <= target <= 109

题目大意：

求四数和等于target。这些数值结果排序后不能重复。

解题思路：

类似于3sum，但需要更加一般化。用递归。不能用求所有笛卡尔积版的Two sum，会TLE。

解题步骤：

N/A

注意事项：

k_sum接口含k_sum(nums, target, k), 基础case为two_sum, 遍历nums每个元素，若重复跳过，将(子数组，target-nums[i], k-1)递归，返回结果拼接
two_sum也是遇到重复元素跳过，若等于target，要左右指针均移动

Python代码：

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
	nums.sort()
	return self.k_sum(nums, target, 4)

def k_sum(self, nums, target, k):
	if k == 2:
		return self.two_sum(nums, target)
	# assume 3 sum
	res = []
	for i in range(len(nums)):
		if i >= 1 and nums[i - 1] == nums[i]: # remember
			continue
		sub_res = self.k_sum(nums[i + 1:], target - nums[i], k - 1)
		for li in sub_res:
			res.append([nums[i]] + li)
	return res

def two_sum(self, nums, target):
	i, j, res = 0, len(nums) - 1, []
	while i < j:
		if (i >= 1 and nums[i - 1] == nums[i]) or nums[i] + nums[j] < target:
			i += 1
		elif (j + 1 < len(nums) and nums[j] == nums[j + 1]) or nums[i] + nums[j] > target:
			j -= 1
		else:
			res.append([nums[i], nums[j]]) # remember to use list rather than tuple
			i += 1 # remember
			j -= 1
	return res

算法分析：

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

LeetCode 244 Shortest Word Distance II

Posted on 2021-12-25 Disqus:

LeetCode

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict. int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

Input
[“WordDistance”, “shortest”, “shortest”]
[[[“practice”, “makes”, “perfect”, “coding”, “makes”]], [“coding”, “practice”], [“makes”, “coding”]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance([“practice”, “makes”, “perfect”, “coding”, “makes”]);
wordDistance.shortest(“coding”, “practice”); // return 3
wordDistance.shortest(“makes”, “coding”);    // return 1

Constraints:

`1 <= wordsDict.length <= 3 10⁴*1 <= wordsDict[i].length <= 10*wordsDict[i]

consists of lowercase English letters.
*

word1andword2are inwordsDict

.
*

word1 != word2* At most5000calls will be made toshortest`.

题目大意：

设计数据结构返回单词列表中两单词下标最短距离。单词列表含重复单词

解题思路：

记录word到下标列表。可以用logn搜索另一个列表，总时间复杂度为O(nlogn)。不如用mergesort的merge来计算，复杂度为O(n)

解题步骤：

N/A

注意事项：

Python代码：

class WordDistance(TestCases):

    def __init__(self, wordsDict: List[str]):
        self.word_to_indices = collections.defaultdict(list)
        for i in range(len(wordsDict)):
            self.word_to_indices[wordsDict[i]].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        indices1 = self.word_to_indices[word1]
        indices2 = self.word_to_indices[word2]
        i, j, res = 0, 0, float('inf')
        while i < len(indices1) and j < len(indices2):
            res = min(res, abs(indices1[i] - indices2[j]))
            if indices1[i] <= indices2[j]:
                i += 1
            else:
                j += 1
        return res

算法分析：

shortest时间复杂度为O(L)，空间复杂度O(1)。L为两单词下标列表的最短长度