专利交易网站建设ppt,品牌商标注册查询官网,优化推荐,珠海市网络营销协会的官方网站#xff08;1462. 课程表 IV leetcode#xff09;广搜拓扑-------------------Java实现
题目表述
你总共需要上 numCourses 门课#xff0c;课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite #xff0c;其中 prerequisites[i] [ai, bi] 表示如果你想…1462. 课程表 IV leetcode广搜拓扑-------------------Java实现
题目表述
你总共需要上 numCourses 门课课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite 其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程你 必须 先选 ai 课程。
有的课会有直接的先修课程比如如果想上课程 1 你必须先上课程 0 那么会以 [0,1] 数对的形式给出先修课程数对。 先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件课程 b 是课程 c 的先决条件那么课程 a 就是课程 c 的先决条件。
你也得到一个数组 queries 其中 queries[j] [uj, vj]。对于第 j 个查询您应该回答课程 uj 是否是课程 vj 的先决条件。
返回一个布尔数组 answer 其中 answer[j] 是第 j 个查询的答案。
样例 条件
2 numCourses 100 0 prerequisites.length (numCourses * (numCourses - 1) / 2) prerequisites[i].length 2 0 ai, bi n - 1 ai ! bi 每一对 [ai, bi] 都 不同 先修课程图中没有环。 1 queries.length 104 0 ui, vi n - 1 ui ! vi
思路
1、广搜拓扑暴力解法其实可以把数据结构由hashset变成二维数组记录这样会省时间空间 建议再做一边。
注意点
ac代码
Java方法一:
class Solution {public ListBoolean checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {HashSetInteger SourceToTarget[] new HashSet[numCourses];HashSetInteger BeforeSource[] new HashSet[numCourses];int source[] new int[numCourses];ListBoolean result new ArrayList();for (int i0;inumCourses;i) {SourceToTarget[i] new HashSet();BeforeSource[i] new HashSet();}for (int[] node:prerequisites)if (!SourceToTarget[node[0]].contains(node[1])) {source[node[1]];SourceToTarget[node[0]].add(node[1]);BeforeSource[node[1]].add(node[0]);}QueueInteger q new LinkedList();for (int i 0;inumCourses;i)if (source[i]0)q.offer(i);while(!q.isEmpty()){int now q.poll();for (Integer target:SourceToTarget[now]){source[target]--;if (source[target]0)q.offer(target);for (Integer s:BeforeSource[now])if (!BeforeSource[target].contains(s))BeforeSource[target].add(s);}}for(int i0;inumCourses;i){for (int s:BeforeSource[i])System.out.print(s );System.out.println();}//judgefor (int i0;iqueries.length;i)if(BeforeSource[queries[i][1]].contains(queries[i][0]))result.add(Boolean.TRUE);elseresult.add(Boolean.FALSE);return result;}
}来源力扣LeetCode 链接https://leetcode-cn.com/problems/squares-of-a-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
