JZX轻语：简
LeetCode 851 - 喧闹和富有
发表于2024年05月15日
首先使用图论将问题抽象出来，将人视作为节点。可以采用DFS的方法解决问题：首先如果a比b富有，则添加有向边b -> a(注意是指向更富的人)，然后通过DFS的方法，求解节点a中，比a富有的人中，quiet值最小的人：首先初始化quiet最小者为自己，然后遍历子节点中quiet值最小者，更新自身的最优解，直至所有节点处理完毕。
同样，此类涉及入度出度的问题可以转化为拓扑排序：如果a比b富有，则添加有向边a -> b(注意这里是指向更穷的人)。不难得知，入度为0的节点意味着没有人比他富有，即属于最富的一批人。但不能使用前缀和的思路解决，因为最富的一批人中，我们不知道他们内部谁比谁有钱(没有边连接他们)。所以，我们可以在拓扑排序的过程中，当处理入度已为0的节点u时，减少其子节点v的入度过程中，顺带更新v中quiet值最小者的数据。这种本质就是从富有到贫穷的顺序开始处理，不断更新穷人(子节点)的数据。
使用DFS的做法：
from collections import deque
class Solution:
def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
n = len(quiet)
adj_list = [[] for _ in range(n)]
for u, v in richer:
adj_list[v].append(u) # v -> u 指向更有钱的人
ans = [-1] * n
def dfs(u: int) -> int:
nonlocal ans
if ans[u] != -1:
return ans[u]
min_quiet_people = u
for v in adj_list[u]:
min_quiet_people_from_v = dfs(v)
if quiet[min_quiet_people_from_v] < quiet[min_quiet_people]:
min_quiet_people = min_quiet_people_from_v
ans[u] = min_quiet_people
return min_quiet_people
for u in range(n):
if ans[u] == -1:
dfs(u)
return ans使用拓扑排序的做法：
from collections import deque
class Solution:
def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
# 拓扑排序: 如果没有人比你有钱 那你就是最有钱的
n = len(quiet)
in_degree = [0] * n
adj_list = [[] for _ in range(n)]
for u, v in richer:
adj_list[u].append(v) # u -> v u比v有钱
in_degree[v] += 1
q = deque()
# 获取最有钱的一批人
for i in range(n):
if in_degree[i] == 0: # 没有入度的 -> 没有比它有钱的
q.append(i)
ans = list(range(n))
while q:
u = q.popleft()
for v in adj_list[u]:
in_degree[v] -= 1
# 在减少入度的时候，顺便更新子节点的数据
if quiet[ans[v]] > quiet[ans[u]]:
ans[v] = ans[u]
if in_degree[v] == 0:
q.append(v)
return ans