leetcode contest 155 writeup

 

概要

比赛链接:leetcode第155周周赛

题目 难度 知识点
最小绝对差 简单
丑数 III 中等 容斥+二分
交换字符串中的元素 中等 并查集
项目管理 困难 拓扑排序

注:思路是理想思路,代码有可能是我比赛时写的,就不那么理想.

所以代码与思路不一定等价

第一题

思路

遍历

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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]))

第二题

思路

容斥原理加上二分法。容斥法确认范围内有几个丑数。二分法右界设为最大值就行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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最终归并成的集合进行排序即可。

并查集一把梭(网上的并查集代码没有导出集合,所以我添了这个,竞赛时没写好超时了,下面的这个版本可以过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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]]))

第四题

思路

不会呀,题都不大看的懂,好像是一个复杂版的拓扑排序,姑且放一个别人的题解吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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

后记

这次竞赛意外繁多,最后就一题过了,其它的都是超时。。。结果竞赛后稍微改了改都能过。。。。

反思一下,其实还是心态崩了,本来都做得出的