第 155 场周赛总结：本期周赛题目质量较高，更多侧重于对思维和常见算法的理解和考察，总体考察的知识点很多，但是代码量除了最后一题以外并不大，适合用作面试题目。
Easy 5197. 最小绝对差
题目
给你个整数数组 arr ，其中每个元素都不相同。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
示例 1：
输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]
示例 2：
输入：arr = [1,3,6,10,15]
输出：[[1,3]]
示例 3：
输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]
题目解析
解法
拿到题目(特别是面试的时候)，我们首先需要保证自己能给出来一个可行解。那么对于这道题目，我们可以按照下列思路来得到一个结果：
- 枚举所有的二元组
<i,j>，计算arr[i]和arr[j]的差，记录其中的最小值。 - 枚举所有的二元组
<i,j>，计算arr[i]和arr[j]的差，将差值等于最小值的二元组记录。 - 将所有二元组按升序排序。
前两步需要遍历所有的二元组，所以计算复杂度为: ，而第三步我们还需要对二元组排序，所以时间复杂度为 。
解法
那么，至少我们现在有一个 的算法了，我们来思考一下有没有什么优化空间。题目要求最小的绝对差，那么如果要差最小的话，两个做差的数一定会是序列排序后相邻的两个数。
基于这个结论，我们可以将整个数组排序，然后计算所有相邻的数的差，再仿照上面的思路求得所有的元素对，现在的思路是：
- 排序数组，枚举所有相邻的二元组
<i,i+1>，计算arr[i]和arr[i+1]的差，记录其中的最小值。 - 枚举所有的二元组
<i,i+1>，计算arr[i]和arr[i+1]的差，将差值等于最小值的二元组记录。 - 将所有二元组按升序排序。
由于我们现在只计算相邻元素的差，所以枚举的时间复杂度从 降为了 ，总体时间复杂度为 。
以下是实现代码:
class Solution(object):
def minimumAbsDifference(self, arr):
"""
:type arr: List[int]
:rtype: List[List[int]]
"""
arr = sorted(arr)
mindiff = min([arr[i]-arr[i-1] for i in range(1,len(arr))])
arr = [[arr[i-1],arr[i]] for i in range(1,len(arr)) if mindiff == arr[i]-arr[i-1]]
return arrMedium 5198. 丑数 III
题目
请你帮忙设计一个程序，用来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的正整数。
示例 1：
输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
示例 2：
输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
题目解析
题目本身来说并不算太难，但是有不少同学被丑数本身的定义绕进去了。这也是算法题目题面中很容易发生的事情，那就是题目所给的定义不一定就是其原有定义。例如我们回到这道题，丑数的定义为能被所给 abc 任一整除的正整数，显然是和之前丑数相关题目是不一样的。在这种时候，我们需要跳开之前的固有思维，来重新考虑在所给条件下，如何求当前的"丑数"。
暴力解法
我们同样有一个可以暴力解决问题的办法，那就是我们从 1 开始枚举，然后看看这个数能不能被 abc 其中某个数整除来判断其是不是丑数，最后到第 n 个丑数就是我们的答案了。这样做的话时间复杂度为 ，由于 n 给的 ，超过了我们说的 的限制，所以显然会超时(当然这和面试能拿到一些分数并不冲突，所以并不是完全没有意义)。
解法
原始问题有 , , 三个因子，我们可以先试图简化问题来寻找灵感。
- 假设我们现在只有一个 a : 例如 等于 2 ，那么丑数序列就是 2 , 4 , 6 , 8 ... ，那么这时如果给了一个数 n ，那么我们知道 中一共有 个丑数，其中 是向下取整。如果 n 也是丑数，那么 n 一定是第 个丑数。
- 假设我们现在有 a 和 b: 例如 等于 2 ， 等于 3 ，那么丑数序列是 2 , 3 , 4 , 6 , 8 , 9 ... ，这时再给一个整数 ， 中又有多少丑数呢？
对于区间 ，他能被 2 整除的数有 个，这些数肯定是丑数没错了，他能被 3 整除的数有 个，这些数也是丑数。但是我们别忘了，还有一些数是能同时被 2 和 3 整除的，也就是能被 6 整除，这些数我们计算了两次。那么减掉这些重复的数以后，剩余的丑数还剩下 个。那么我们知道，在 区间内有这么多丑数。
我们现在可以回到原问题的三个数了，这就是一个典型的容斥原理了，如下图，对于 3 个数的情况，对应的丑数数量为 ，其中 是最小公倍数。通过这个公式，我们可以方便的求出 中的丑数数量。
{:align=center}
但是这离我们解决问题还有一段距离，我们现在想知道的是第 个丑数是什么，而不是 中有多少丑数。我们来思考一下对于第 个丑数 来说，他会满足什么性质：
- 显然 中有 个丑数。
- 中有 个丑数。
那么由于随着数的变大，丑数的数量肯定是单调递增的，那么我们可以利用二分查找来逐步逼近某个临界点，满足 有 个丑数且 中有 个丑数。这样时间复杂度仅为二分查找的时间复杂度 。
还有一点是关于最大公约数的实现，代码里是直接调的系统库，但是我们也需要知道最大公约数是有 级别的实现方法的，文末也会给出相关资料 [1] 。
以下是实现代码:
from fractions import gcd
class Solution(object):
def nthUglyNumber(self, n, a, b, c):
"""
:type n: int
:type a: int
:type b: int
:type c: int
:rtype: int
"""
//最小公倍数
def lcm(a,b):
return a*b/gcd(a,b)
//计算[1,mid]有多少丑数
//这种实现时间复杂度会高一个log(n)数量级，最小公倍数可以预处理。
def get_idx(mid):
return mid // a + mid // b + mid // c - mid //lcm(a,b) - mid//lcm(b,c) - mid //lcm(c,a) + mid//lcm(lcm(a,b),c)
l = 1; r = 2*10**9+1
while ( l < r ):
mid = (l+r+1)/2
idx = get_idx(mid)
if idx == n:
l = mid
break
elif idx < n:
l = mid
elif idx > n:
r = mid-1
//这里的实现略微有些不一样，可以思考一下现在的做法
return l-min(l%a,min(l%b,l%c))Medium 5199. 交换字符串中的元素
题目
给你一个字符串s，以及该字符串中的一些「索引对」数组 pairs，其中pairs[i] = [a, b]表示字符串中的两个索引（编号从0开始）。
你可以任意多次交换在pairs中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 1:
输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
示例 2：
输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
题目解析
这道题理论上我们也是可以暴力的：搜索所有的交换然后同时保留我们的中间状态，记录全部状态的字典序最小值，但是这样的话是一个指数级别复杂度的算法了。
考虑一个字符串 ，如果他的位置 和 能交换，且 和 能交换，那么由于我们的交换没有限制，我们可以把 三个位置排成任意我们想要的排列。
这里我们可以简单证明一下，对于 和 能交换的情况，我们可以得到 和 两种排列，即 2 个数的时候我们可以得到任意排列。
那么三个数的时候，例如 ，由于 2 个数的时候我们可以得到任意排列，那么我们最后把 c 不停地向前交换，可以把 c 放在任意位置，也即是 3 个数我们也可以得到任意排列。我们还可以继续推广一下，如果有 ，对于 位置的字母，我们可以得到其任意排列。
这个结论就很有作用了，令 ，由于我们需要原始字符串最小，那么对于 位置的字母，肯定是将其重排为字典序最小字符串，如下图。
{:align=center}
那么原问题就可以分为两步：
- 得到每个点所属的 集合
- 将所有 集合中的字符重排为字典序最小排列。
先来解决第一个问题，我们要知道哪些点属于同一个 集合，那么对于所有给的边 ，我们知道 是属于一个集合的，如果集合还有边连向外面例如 ，我们知道 也属于这个集合。这种问题特性我们可以使用并查集来进行维护，最后得到每个点所属的集合 id 。对于不了解并查集的同学，这里也整理了一些资料 [2]。
而第二个问题就很简单了，我们直接将对应位置的字符进行排序即可。
并查集时间复杂度为 ，排序时间复杂度为 ，所以总体时间复杂度为 ，当然，由于这里是字符串排序，我们可以使用桶排序来将时间复杂度优化为 。
下面是实现代码：
import numpy as np
class Solution(object):
def smallestStringWithSwaps(self, s, pairs):
"""
:type s: str
:type pairs: List[List[int]]
:rtype: str
"""
#并查集的find函数
def ffind(a):
if a == fa[a]:
return a
f = ffind(fa[a])
fa[a] = f
return f
#并查集的union函数
def union(a,b):
a = ffind(a)
b = ffind(b)
fa[a] = b
#并查集维护集合
n = len(s)
fa = np.arange(n)
for a,b in pairs:
union(a,b)
for i in range(n):
ffind(i)
#得到所有place集合
unique_fa = np.unique(fa)
#得到所有place集合中对应的字符串并排序
fa_str = {x:'' for x in unique_fa}
for i in range(n):
fa_str[fa[i]] += s[i]
for x in unique_fa:
fa_str[x] = sorted(fa_str[x])
fa_cnt = {x:0 for x in unique_fa}
#将排序完的字符串反映射回原串得到最后结果
ans = ''
for i in range(n):
x = fa[i]
ans += fa_str[x][fa_cnt[x]]
fa_cnt[x] += 1
return ansHard 5200. 项目管理
提示：该题难度略小于 hard，可以尝试
题目
公司共有 n 个项目和 m 个小组，每个项目要不没有归属，要不就由其中的一个小组负责。
我们用 group[i] 代表第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）
请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
同一小组的项目，排序后在列表中彼此相邻。
项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
结果要求：
如果存在多个解决方案，只需要返回其中任意一个即可。
如果没有合适的解决方案，就请返回一个空列表。
示例 1：
输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]
示例 2：
输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。
题目解析
这道题是一道拓扑排序的变种，本身虽然比较复杂但是理清楚了并不是特别难，之所以被排到 hard 可能是因为题目实在是太难懂了~ ~。
在读了十多遍题目以后大概理解了这道题要我们做什么：
- 有很多任务，任务分成了若干个组，一个组的任务必须要连续做完，不能先做组 的任务，然后去做组 的，然后又跑来做组 的。
- 任务之间有一些依赖关系，对于每个任务给了其依赖任务，需要所有依赖任务完成后才能开始该任务，例如
1:[2,6]，那么任务 需要在任务 和任务 都完成以后才能开始。 - 最后，我们还是要一个合法的任务序列，保证依赖关系不冲突，且组内的任务是连着做的。
那么根据这些条件，一个可能的依赖情况是这样的：
{:align=center}
我们看到，依赖关系实际上分为两种，一种是组内依赖关系(红色箭头)，一种是组间依赖关系(绿色箭头)。由于一个组的任务需要连着做，我们先不考虑组内依赖关系，那么从组的角度来看：
{:align=center}
这就是一个典型的拓扑排序问题了！我们可以很容易的求出可行的调度序列，当然这个序列是组级别的，也即是我们先执行哪个组的任务，再执行哪个组的任务的序列。
那么组的执行顺序知道了，接下来我们只需要看每个组内的任务该如何执行就可以了。如下图，对于一个组内的任务，我们发现他还是一个朴素的拓扑排序问题：
那么接下里的思路也有了，我们对于每个组内的任务再分别建图求拓扑序，最后根据组级别的拓扑序将结果整合起来就可以了。当然，如果任一个拓扑排序发现无可行解，那么整个系统就无可行解。
总体时间复杂度为 。
以下为实现代码：
import Queue
import numpy as np
class Solution(object):
def sortItems(self, n, m, group, beforeItems):
"""
:type n: int
:type m: int
:type group: List[int]
:type beforeItems: List[List[int]]
:rtype: List[int]
"""
#组内拓扑排序
def get_group_ans(group_points,group_edges):
#组内级别建图
graph = {group_point:[] for group_point in group_points}
degree = {group_point:0 for group_point in group_points}
for x,y in group_edges:
graph[y].append(x)
degree[x] += 1
#top sort
q = Queue.Queue()
for graph_point in group_points:
if degree[graph_point] == 0:
q.put(graph_point)
#组内拓扑排序
task_res = []
while not q.empty():
x = q.get()
task_res.append(x)
for y in graph[x]:
degree[y] -= 1
if degree[y] == 0:
q.put(y)
if len(task_res) != len(group_points):
return None
return task_res
group_cnt = max(group)+1
for i in range(n):
if group[i] == -1:
group[i] = group_cnt
group_cnt += 1
#组级别建图
group_ids = np.unique(group)
graph = {group_id:[] for group_id in group_ids}
degree = {group_id:0 for group_id in group_ids}
group_inner_edges = {group_id:[] for group_id in group_ids}
group_points = {group_id:[] for group_id in group_ids}
for i in range(n):
groupa = group[i]
group_points[groupa].append(i)
for j in beforeItems[i]:
groupb = group[j]
if groupa == groupb:
group_inner_edges[groupa].append([i,j])
continue
graph[groupb].append(groupa)
degree[groupa] += 1
#组级别拓扑排序
q = Queue.Queue()
for group_id in group_ids:
if degree[group_id] == 0:
q.put(group_id)
group_res = []
while not q.empty():
x = q.get()
group_res.append(x)
for y in graph[x]:
degree[y] -= 1
if degree[y] == 0:
q.put(y)
if len(group_res) != len(group_ids):
return []
#根据组拓扑序整合结果
task_res = []
for group_id in group_res:
ans = get_group_ans(group_points[group_id],group_inner_edges[group_id])
if ans is None:
return []
task_res += ans
return task_res相关参考
