有个算法题想问下各位

今天面试给了个算法题,想问下各位,有N个小球,编号为1-N。给一个需求列表,每个需求列表有两个小球。求最多能满足几个需求。
例如N = 4, requests = [[1,2],[3,4],[2,3]]  答案是2, 因为选择[1,2]  [3,4]
#面试复盘#
全部评论
我昨天晚上写出来了。 N = 19 global ans ans = 0 requests = [[1,2],[3,4],[2,3],[1,5],[1,6],[2,4],[5,6],[2,19],[13,15],[10,11],[1,10]] def find(N, requests):     nums = [1] * N     ans = 0     for i in range(len(requests)):         index = i         used = set()         count = 0         while index < len(requests):             cur = requests[index]             if cur[0] not in used and cur[1] not in used:                 used.add(cur[0])                 used.add(cur[1])                 count += 1             index += 1         print(used)         ans = max(ans, count)     return ans print(find(N,requests))
点赞 回复 分享
发布于 2022-05-28 10:10
开一个n的数组,把requests里的每一对数都按照值放到n数组对应位置,若之前该位置未被放入则放入成功修改该位置标记,若该位置已放入过则跳到下一个需求,另外可以记录一个已放入数量,若已经放满,则直接结束循环,时间复杂度n,空间复杂度n
点赞 回复 分享
发布于 2022-05-28 09:54

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务