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