四川建设数字证书网站,江西龙峰建设集团的网站,ccd设计公司很厉害吗,做个网站好还是做淘宝好文章目录1. 题目2. 解题1. 题目
公司共有 n 个项目和 m 个小组#xff0c;每个项目要不无人接手#xff0c;要不就由 m 个小组之一负责。
group[i] 表示第 i 个项目所属的小组#xff0c;如果这个项目目前无人接手#xff0c;那么 group[i] 就等于 -1。#xff08;项目和…
文章目录1. 题目2. 解题1. 题目
公司共有 n 个项目和 m 个小组每个项目要不无人接手要不就由 m 个小组之一负责。
group[i] 表示第 i 个项目所属的小组如果这个项目目前无人接手那么 group[i] 就等于 -1。项目和小组都是从零开始编号的小组可能存在没有接手任何项目的情况。
请你帮忙按要求安排这些项目的进度并返回排序后的项目列表
同一小组的项目排序后在列表中彼此相邻。项目之间存在一定的依赖关系我们用一个列表 beforeItems 来表示其中 beforeItems[i] 表示在进行第 i 个项目前位于第 i 个项目左侧应该完成的所有项目。
如果存在多个解决方案只需要返回其中任意一个即可。 如果没有合适的解决方案就请返回一个 空列表 。
示例 1
输入n 8, m 2,
group [-1,-1,1,0,0,1,0,-1],
beforeItems [[],[6],[5],[6],[3,6],[],[],[]]
输出[6,3,4,1,5,2,0,7]
示例 2输入n 8, m 2,
group [-1,-1,1,0,0,1,0,-1],
beforeItems [[],[6],[5],[6],[3],[],[4],[]]
输出[]
解释与示例 1 大致相同但是在排序后的列表中4 必须放在 6 的前面。提示
1 m n 3 * 10^4
group.length beforeItems.length n
-1 group[i] m - 1
0 beforeItems[i].length n - 1
0 beforeItems[i][j] n - 1
i ! beforeItems[i][j]
beforeItems[i] 不含重复元素来源力扣LeetCode 链接https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
拓扑排序学习、及相关题目
两次拓扑排序即可
class Solution {
public:vectorint sortItems(int n, int m, vectorint group, vectorvectorint beforeItems) {for(int i 0; i n; i){if(group[i] -1)group[i] m;//无人接管的分配一个虚拟团队号}vectorvectorint itemgraph(n);vectorvectorint groupgraph(m);vectorint itemIndegree(n, 0);vectorint groupIndegree(m, 0);for(int i 0; i n; i){for(auto j : beforeItems[i]){itemgraph[j].push_back(i);//建图itemIndegree[i];//记录出入度if(group[i] ! group[j]) // 注意条件{ // 团队也建图记录出入度groupgraph[group[j]].push_back(group[i]);groupIndegree[group[i]];}}}vectorvectorint g_items(m);// item 拓扑排序queueint q;for(int i 0; i n; i)if(itemIndegree[i] 0)q.push(i);int countItem 0;while(!q.empty()){int i q.front();q.pop();countItem;g_items[group[i]].push_back(i);//每个item顺序存入自己的团队for(auto j : itemgraph[i]){if(--itemIndegree[j]0)q.push(j);}}if(countItem ! n)return {};// 团队拓扑排序vectorint g_order;for(int i 0; i m; i)if(groupIndegree[i] 0)q.push(i);int countgroup 0;while(!q.empty()){int g q.front();q.pop();countgroup;g_order.push_back(g);for(auto j : groupgraph[g]){if(--groupIndegree[j]0)q.push(j);}}if(countgroup ! m)return {};// 写入答案vectorint ans(n);int idx 0;for(auto g : g_order){for(auto i : g_items[g])ans[idx] i;}return ans;}
};200 ms 43 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
