首页 > 试题广场 >

体育课测验(一)

[编程题]体育课测验(一)

热度指数：724 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

体育课共有 $numProject$ 个考核项目，编号为 $0$ 到 $numProject - 1$ ，考核中每两个项目被划分为一组得到分组数组 $groups_{i}$ ，现规定若想完成项目 $groups_{i}[0]$ ，必须先完成 $groups_{i}[1]$ 。保证所有分组互不相同，若分组情况能顺利完成考核，请返回true否则返回false。

数据范围：

$1\leq numProject \leq 10^5$
$1\leq groups_{i}.length \leq 5000$

示例1

输入

3,[[2,1]]

输出

true

说明

要先完成1号项目，再完成2号项目，而0号项目不受约束，故可以完成项目返回Yes

示例2

输入

3,[[1,0], [0,1]]

输出

false

说明

第一个分组要求先完成0号项目，再完成1号项目；而第二个分组要求先完成1号项目，再完成0号项目，自相矛盾，故不可以完成项目返回No

算法知识视频讲解

Python3

牛客976294号

class Solution:
    def canFinish(self , numProject: int, groups: List[List[int]]) -> bool:
        # write code here
        projects = {x:0 for x in range(numProject)}
        while len(projects) > 0:
            for a, b in groups:
                if a in projects and b in projects:
                    projects[a] = 1
            
            valid = False
            for i in list(projects.keys()):
                if projects[i] == 0:
                    valid = True
                    del projects[i]
            if not valid:
                break
            projects = {x:0 for x in projects}
        return len(projects) == 0

发表于 2023-10-24 14:38:56 回复(0)