leetcode contest 155 writeup
概要
比赛链接:leetcode第155周周赛
| 题目 | 难度 | 知识点 |
|---|---|---|
| 最小绝对差 | 简单 | 无 |
| 丑数 III | 中等 | 容斥+二分 |
| 交换字符串中的元素 | 中等 | 并查集 |
| 项目管理 | 困难 | 拓扑排序 |
注:思路是理想思路,代码有可能是我比赛时写的,就不那么理想.
所以代码与思路不一定等价
第一题
思路
遍历
代码
from typing import List
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
arr.sort()
min = arr[1] - arr[0]
for i in range(len(arr) - 1):
i_ = abs(arr[i + 1] - arr[i])
if min > i_:
min = i_
re = []
for i in range(len(arr) - 1):
i_ = abs(arr[i + 1] - arr[i])
if min == i_:
re.append([arr[i],arr[i+1]])
return re
s = Solution()
print(s.minimumAbsDifference([3,8,-10,23,19,-4,-14,27]))
第二题
思路
容斥原理加上二分法。容斥法确认范围内有几个丑数。二分法右界设为最大值就行。
代码
def lcm(x, y):
# 获取最大的数
return x * y / gcd(x, y)
def gcd(m, n):
if not n:
return m
else:
return gcd(n, m % n)
class Solution:
def low(self, n: int, a: int, b: int, c: int) -> int: # [1,n]内含有几个丑数
return n // a + n // b + n // c - n // lcm(a, b) - n // lcm(a, c) - n // lcm(b, c) + n // lcm(lcm(a, b), c)
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
l = 1
r = 2 * 10 ** 9 + 1
m = None
while True:
mid = (l + r) // 2
mid_v = self.low(mid, a, b, c)
if mid_v == n:
m = mid
break
if mid_v < n:
l = mid + 1
else:
r = mid - 1
while not (self.low(m, a, b, c) == n and self.low(m - 1, a, b, c) == n - 1):
m -= 1
return m
s = Solution()
# print(s.nthUglyNumber(5, 2, 11, 13))
print(s.nthUglyNumber(1000000000,
2,
217983653,
336916467))
第三题
思路
首先我们知道如果数组内索引1和2对应的数可以随意调换，索引2和3对应的数可以随意调换的话，那么等价于索引1、2、3对应的数可以任意调换，以此类推。
也就是我们只需求求出groups最终归并成的集合进行排序即可。
并查集一把梭（网上的并查集代码没有导出集合，所以我添了这个，竞赛时没写好超时了，下面的这个版本可以过。
代码
from typing import *
class unionfind:
def __init__(self, groups):
self.groups = groups
self.items = []
for g in groups:
self.items += list(g)
self.items = set(self.items)
self.parent = {}
self.rootdict = {} # 记住每个root下节点的数量
for item in self.items:
self.rootdict[item] = 1
self.parent[item] = item
def union(self, r1, r2):
rr1 = self.findroot(r1)
rr2 = self.findroot(r2)
cr1 = self.rootdict[rr1]
cr2 = self.rootdict[rr2]
if cr1 >= cr2: # 将节点数量较小的树归并给节点数更大的树
self.parent[rr2] = rr1
self.rootdict.pop(rr2)
self.rootdict[rr1] = cr1 + cr2
else:
self.parent[rr1] = rr2
self.rootdict.pop(rr1)
self.rootdict[rr2] = cr1 + cr2
def is_connected(self, i, j):
return self.findroot(i) == self.findroot(j)
def findroot(self, r):
"""
可以通过压缩路径来优化算法,即遍历路径上的每个节点直接指向根节点
"""
if r in self.rootdict.keys():
return r
else:
return self.findroot(self.parent[r])
def createtree(self):
for g in self.groups:
if len(g) < 2:
continue
else:
for i in range(0, len(g) - 1):
if self.findroot(g[i]) != self.findroot(g[i + 1]): # 如果处于同一个集合的节点有不同的根节点，归并之
self.union(g[i], g[i + 1])
def to_lists(self):
re: Dict[List] = {}
for k in self.rootdict:
re[k] = []
for n in self.parent:
re[self.findroot(n)].append(n)
r = []
for k in re:
r.append(re[k])
return r
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
u = unionfind(pairs)
u.createtree()
a = u.to_lists()
li = list(s)
for se in a:
keys = list(se)
keys.sort()
values = [li[x] for x in keys]
values.sort()
for i, v in zip(keys, values):
li[i] = v
return "".join(li)
s = Solution()
print(s.smallestStringWithSwaps("dcab", [[0, 3], [1, 2], [0, 2]]))
第四题
思路
不会呀，题都不大看的懂，好像是一个复杂版的拓扑排序，姑且放一个别人的题解吧
代码
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
后记
这次竞赛意外繁多，最后就一题过了，其它的都是超时。。。结果竞赛后稍微改了改都能过。。。。
反思一下，其实还是心态崩了，本来都做得出的