[数据结构与算法][Leetcode] 每日两题 851 1603 -day41

851. 喧闹和富有

方法一 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

1603. 设计停车系统

用一个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