首页 > 试题广场 >

体育课测验(一)

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

热度指数：884 时间限制：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

算法知识视频讲解

Java

牛客499848474号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numProject int整型
     * @param groups int整型ArrayList<ArrayList<>>
     * @return bool布尔型
     */
    public boolean canFinish (int numProject,
        ArrayList<ArrayList<Integer>> groups) {
        // write code here
        int[] indegree = new int[numProject];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < groups.size(); i++) {
            int p = groups.get(i).get(1);
            int q = groups.get(i).get(0);
            if (map.containsKey(p)) {
                map.get(p).add(q);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(q);
                map.put(p, list);
            }
            indegree[q]++;
        }
        //each course in this queue has no dependency on other courses.
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numProject; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        int res = 0;
        while (!queue.isEmpty()) {
            int c = queue.poll();
            res++;
            if (map.containsKey(c)) {
                List<Integer> dep = map.get(c);
                for (int cc : dep) {
                    indegree[cc]--;
                    if (indegree[cc] == 0) queue.offer(cc);
                }
            }
        }
        return res == numProject;
    }
}

发表于 2025-01-07 09:22:38 回复(0)

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)