方法一 DFS 先记录每个节点的直接指向节点,也就相当于所有的边,然后对于每个节点,深度优先搜索他的子节点,直到没有子节点,然后逐一返回,判断该父节点的当前值是否小于其子节点的当前值,若是,则将子节点的值答案替换
class Solution: def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]: n = len(quiet) lis = [[i,quiet[i]] for i in range(n)] #print(lis) dic = defaultdict(list) for tis,oth in richer: dic[oth].append(tis) def dfs(child): if lis[child][0] != child : return if child not in dic: return for node in dic[child]: dfs(node) if lis[node][1] < lis[child][1]: lis[child][0],lis[child][1] =lis[node][0],lis[node][1] for i in range(n): dfs(i) return [x[0] for x in lis]
方法二 拓扑排序 先构建所有的边 并且统计每个节点的入度, 首先将所有入度为0的点加入队列(这些点都是富有的)对于他们能够到达的节点 也就是比他们贫穷的点, 如果 富有点的值小于 平穷点,那么将其替换,并且将该平穷点的入度减一 ,同时判断是否入度为0
class Solution: def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]: n = len(quiet) deg = [0]*n res = [i for i in range(n)] dic = defaultdict(list) for rich,poor in richer: dic[rich].append(poor) deg[poor] +=1 q = [] for x in range(n): if deg[x] == 0: q.append(x) while q: rich = q[0] del q[0] for poor in dic[rich]: if quiet[res[rich]] < quiet[res[poor]]: res[poor] = res[rich] deg[poor] -= 1 if deg[poor] == 0: q.append(poor) return res
用一个list去记录当前的大中小三种停车位的个数然后判断
class ParkingSystem: def __init__(self, big: int, medium: int, small: int): self.lis = [big,medium,small] def addCar(self, carType: int) -> bool: if self.lis[carType-1] >0: self.lis[carType-1] -=1 return True return False