Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
一共有n个楼,给出一些requests,requestsi=[fromi, toi],代表一个人要求从from到to楼,问最多可以满足多少个requests,使得最后每栋楼进出的人数一样
直接DFS爆搜


 1 #1601
 2 #Runtime: 1254 ms (Beats 62.13%)
 3 #Memory: 16.6 MB (Beats 33.98%)
 4 
 5 class Solution:
 6     def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
 7         ans = 0
 8         remain = [0] * n
 9 
10         def DFS(x, cnt):
11             nonlocal ans
12             if x == len(requests):
13                 for i in range(n):
14                     if remain[i]:
15                         return
16                 ans = max(ans, cnt)
17                 return
18             remain[requests[x][0]] -= 1
19             remain[requests[x][1]] += 1
20             DFS(x + 1, cnt + 1)
21             remain[requests[x][0]] += 1
22             remain[requests[x][1]] -= 1
23             DFS(x + 1, cnt)
24 
25         DFS(0, 0)
26         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理