本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3606. 优惠券校验器 - 力扣（LeetCode）
解题思路
模拟即可
示例代码
python
class Solution:
def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
d = {"electronics": 0, "grocery": 1, "pharmacy": 2, "restaurant": 3}
def check(s):
for c in s:
if c != '_' and not c.isalpha() and not c.isdigit():
return False
return len(s) > 0
ans = []
for s, b, f in zip(code, businessLine, isActive):
if check(s) and b in d and f:
ans.append((s, b))
ans.sort(key=lambda p: (d[p[1]], p[0]))
return [s for s, _ in ans]3607. 电网维护 - 力扣（LeetCode）
解题思路
查找连通块，用 dfs 或用并查集，而后用堆维护每一个连通块的最小编号（懒删除）
示例代码
python
class Solution:
def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
g = [[] for _ in range(c + 1)]
for u, v in connections:
g[u].append(v)
g[v].append(u)
def dfs(x, fa):
for y in g[x]:
if y in vis or y == fa:
continue
heappush(hs[-1], y)
d[y] = len(hs) - 1
vis.add(y)
dfs(y, x)
return
vis = set()
hs = []
d = {}
for i in range(1, c + 1):
if i not in vis:
hs.append([])
vis.add(i)
heappush(hs[-1], i)
d[i] = len(hs) - 1
dfs(i, 0)
ans = []
dis = set()
for op, x in queries:
if op == 1:
if x not in dis:
ans.append(x)
else:
ans.append(-1)
if x not in d:
continue
while hs[d[x]]:
y = hs[d[x]][0]
if y in dis:
heappop(hs[d[x]])
else:
ans[-1] = y
break
else:
dis.add(x)
return anspython
class Solution:
def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
uf = UnionFind(c + 1)
for u, v in connections:
uf.union_rank(u, v)
hs = [[] for _ in range(c + 1)]
for i in range(1, c + 1):
hs[uf.find(i)].append(i)
ans = []
dis = set()
for op, u in queries:
if op == 1:
if u not in dis:
ans.append(u)
else:
ans.append(-1)
v = uf.find(u)
while hs[v]:
if hs[v][0] in dis:
heappop(hs[v])
else:
ans[-1] = hs[v][0]
break
else:
dis.add(u)
return ans3608. 包含 K 个连通分量需要的最小时间 - 力扣（LeetCode）
解题思路
正难则反，按消失时间排序边，遍历加入并查集，当连通块个数小于 k 时退出遍历或返回答案
示例代码
python
class Solution:
def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
edges.sort(key=lambda p: -p[-1])
uf = UnionFind(n)
cnt = n
for u, v, t in edges:
if not uf.connected(u, v):
cnt -= 1
uf.union_rank(u, v)
if cnt and cnt < k:
return t
return 0py
class UnionFind:
def __init__(self, n: int) -> None:
self.n = n
self.parent = list(range(n))
self.rank = [1] * n
self.size = [1] * n
def find(self, x: int) -> int:
if self.parent[x] == x:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union_by_size(self, x: int, y: int) -> None:
x_root, y_root = self.find(x), self.find(y)
if x_root != y_root:
if self.size[y_root] <= self.size[x_root]:
self.parent[y_root] = x_root
self.size[x_root] += self.size[y_root]
else:
self.parent[x_root] = y_root
self.size[y_root] += self.size[x_root]
def union_rank(self, x: int, y: int) -> None:
x_root, y_root = self.find(x), self.find(y)
if x_root != y_root:
if self.rank[y_root] <= self.rank[x_root]:
self.parent[y_root] = x_root
else:
self.parent[x_root] = y_root
if self.rank[x_root] == self.rank[y_root]:
self.rank[x_root] += 1
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)3609. 到达目标点的最小移动次数 - 力扣（LeetCode）
解题思路
脑筋急转弯，正难则反，计算 (tx, ty) -> (sx, sy)的最小移动次数
示例代码
python
class Solution:
def minMoves(self, sx: int, sy: int, tx: int, ty: int) -> int:
q = [(tx, ty)]
ans = 0
while q:
tmp = q
q = []
for x, y in tmp:
if x == sx and y == sy:
return ans
if x < sx or y < sy:
continue
if x > y:
if x >= y * 2:
if x % 2 == 0:
q.append((x // 2, y))
else:
q.append((x - y, y))
elif x < y:
if y >= x * 2:
if y % 2 == 0:
q.append((x, y // 2))
else:
q.append((x, y - x))
else:
q.append((x, y - x))
q.append((x - y, y))
ans += 1
return -1