讨论/题目交流/🏆 第 155 场力扣周赛/
🏆 第 155 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。
image.png

展开讨论

力扣周赛 155 第四题题解

本题考察拓扑排序。拓扑排序是图论中的基本算法,其基本步骤是:

  • 以邻接表形式存储图,同时计算出每个点的入度。入度的计算可以在连边时顺带完成。
  • 将所有入度为 00。的点入队。
  • 对于队列中的每一个点,将其输出后出队,然后遍历以它为起点的每一条边,将对应终点的入度减去 11。如果终点的入度变为 00,则将终点入队。
  • 直到队列为空。

如果此时所有顶点都已经被输出,那么就得到了一个可行的拓扑序列。如果还有未被输出的顶点,代表图中一定有环(对应本题的无解情形)。

下面具体看这道题。

  • 任务被分成了若干组,每组内的任务必须相邻,这实际上提示我们要对组进行一个排序。
  • 每个任务有若干前置任务。这里需要考虑两种情形。
    1. 前置任务和当前任务在不同的组中。这就构成了两个任务组之前的拓扑关系。
    2. 前置任务和当前任务在同一个组中。这就构成了同一个任务组中两个任务间的拓扑关系。

由于还有一些任务是不成组的(组为 −1-1),我们进行预先处理,把这些任务当成只含有一个任务的组,以便后面进行统一处理。

根据上面的分析,我们知道,需要构建两个级别的图:

  1. 组级的,需要构建 11 个。
  2. 组内的,需要构建 m+km+k 个(kk 为不成组的任务的个数)

建立好图后,我们首先进行组级的拓扑排序,得到组的序列。
然后,我们对每一个组分别进行拓扑排序,得到组内的序列,并将其加入到最后的结果中。

如果任意一次拓扑排序没有成功进行(输出的点的数目少于点的总数),就说明无解,返回一个空数组。
如果全都顺利进行,我们就得到了一个可行的解。

思考 本题只要求给出一个可行解。如果要求给出一个字典序最小的解,需要对上述代码进行怎样的调整?

class Graph {
    unordered_map<int, vector<int>> adj;
    unordered_map<int, int> indegree;
public:
    Graph() {}
    
    Graph(int n) {
        adj = unordered_map<int, vector<int>>{};
        indegree = unordered_map<int, int>{};
        for (int i = 0; i < n; ++i) {
            indegree[i] = 0;
            adj[i] = vector<int>{};
        }
    }
    
    Graph(vector<int> &vec) {
        adj = unordered_map<int, vector<int>>{};
        indegree = unordered_map<int, int>{};
        for (const int &i : vec) {
            indegree[i] = 0;
            adj[i] = vector<int>{};
        }
    }
    
    void addEdge(int from, int to) {
        adj[from].push_back(to);
        indegree[to]++;
    }
    
    vector<int> sort() {
        queue<int> q;
        vector<int> ans;
        for (const auto &p : indegree) {
            if (p.second == 0) q.push(p.first);
        }
        
        int cnt = 0;
        while (!q.empty()) {
            int h = q.front();
            q.pop();
            ans.push_back(h);
            cnt++;
            for (const auto &i : adj[h]) {
                indegree[i]--;
                if (indegree[i] == 0) q.push(i);
            }
        }
        
        return ans;
    }
};

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItems(m, vector<int>{});
        for (int i = 0; i < n; ++i) {
            if (group[i] >= 0) groupItems[group[i]].push_back(i);
            else {
                // 单独的任务(不成组的),每一个单独放到一个组中。
                group[i] = groupItems.size();
                groupItems.push_back(vector<int>{i});
            }
        }
        
        Graph groupGraph = Graph(groupItems.size());
        vector<Graph> groupItemGraphs(groupItems.size());
        for (int i = 0; i < groupItems.size(); ++i) {
            groupItemGraphs[i] = Graph(groupItems[i]);
        }
        for (int i = 0; i < n; ++i) {
            for (const int &item : beforeItems[i]) {          
                int gi = group[i];
                if (gi == group[item]) {
                    // 前置任务在同一个组中,设置组内拓扑关系。
                    groupItemGraphs[gi].addEdge(item, i);
                } else {
                    // 前置任务在另一个组中,设置组间拓扑关系。
                    groupGraph.addEdge(group[item], gi);
                }
            }
        }

        vector<int> groupOrder = groupGraph.sort();
        vector<int> ans;
        if (groupOrder.size() < groupItems.size()) return ans;
        for (const int &i : groupOrder) {
            vector<int> order = groupItemGraphs[i].sort();
            if (order.size() < groupItems[i].size()) return vector<int>{};
            else for(const int &j : order) ans.push_back(j);
        }
        return ans;
    }
};
3
展开全部 14 讨论