228周赛好题分享

本场周赛在国际服打的,应该算比较简单。A了三题,第四题因为同学聚会跑路了,应该是铁铁的ak的。

因为题都会做,也没啥好分享的。

5678. 袋子里最少数目的球

出烂的二分。二分答案,每次判断当前这个最大值,是否满足划分。

class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:

def check(n):
c = 0
for a in nums:
if a <= n: continue
else:
x = 0
x = math.ceil(a/n) - 1
c += x
return c <= maxOperations

l = 1
r = max(nums)

while l < r:
mid = l + (r-l)//2
if check(mid): r = mid
else: l = mid + 1
return l

5679. 一个图中连通三元组的最小度数

这题没啥好说的,就是枚举三元对,判断是否成环,成环算一下度数。。刚开始用的临界表,超时md。最后换成邻接矩阵直接过的。

class Solution:
def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
adj = [[0] * n for _ in range(n)]
degree = [0] * n
for u,v in edges:
adj[u-1][v-1] = 1
adj[v-1][u-1] = 1
degree[u-1] += 1
degree[v-1] += 1
res = float('inf')
for i in range(1,n+1):
for j in range(i+1,n+1):
for k in range(j+1,n+1):
if adj[i-1][j-1] == 1 and adj[j-1][k-1] == 1 and adj[i-1][k-1]:
if degree[i-1] + degree[j-1] + degree[k-1] - 6 == 0:
return 0
else:
res = min(res,degree[i-1] + degree[j-1] + degree[k-1] - 6)
if res == float('inf'):
return -1
return res