编译依赖问题

利用优先队列实现拓扑排序，代码仅供参考

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串 
     * @return string字符串
     */
    public String compileSeq (String input) {
        // write code here
        String[] items = input.split(",");
        int n = items.length;
        int[] pre = new int[n];
        PriorityQueue queue = new PriorityQueue(n);
        boolean[] vis = new boolean[n];
        for (int i = n - 1; i >= 0; --i) {
            pre[i] = Integer.parseInt(items[i]);
            if (pre[i] == -1) {
                queue.offer(i);
            }
        }
        StringBuilder builder = new StringBuilder(2 * n);
        while (!queue.isEmpty()) {
            Integer e = queue.poll();
            vis[e] = true;
            builder.append(e + ",");
            for (int i = n - 1; i >= 0; --i) {
                if (!vis[i] && pre[i] == e) {
                    pre[i] = -1;
                    queue.offer(i);
                }
            }
        }
        builder.deleteCharAt(builder.length() - 1);
        return builder.toString();
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串
     * @return string字符串
     */
    public String compileSeq (String input) {
        //定义一个优先队列，存放所有没有依赖的元素（从小到大排序）
        //Queue存储出度为0的节点
        PriorityQueue<Integer> queue=new PriorityQueue<>(((o1, o2) -> o1-o2));

        String[] split = input.split(",");
        int n=split.length;
        int[] nums=new int[n];
        
        for(int i=0;i<n;i++){
            nums[i]=Integer.parseInt(split[i]);
        }
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < n; i++) {
            //将没有依赖的元素放入队列中
            if(nums[i]==-1)queue.offer(i);
        }
        
        while(!queue.isEmpty()){
            int x = queue.poll();
            sb.append(x+",");
            
            //当完成编译完成后，依赖该文件的文件此时也不存在依赖了
            //例如:加入A依赖B，当B完成编译后，A也不存在依赖了
            //将其加入到队列中
            for (int i = 0; i < n; i++) {
                if(nums[i]==x) queue.offer(i);
            }
        }
        sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串 
     * @return string字符串
     */
    string compileSeq(string s) {
        // write code here
        int m=s.length();
        vector<int> nums;
        int j=0;
        while(j<m){
            string number;
            while(j<m&&s[j]!=','){
                number+=s[j];
                j++;
            }
            if(number[0]!='-'){
                nums.push_back(stoi(number));
            }
            else
                nums.push_back(-1);
            j++;
        }
        int n=nums.size();
        vector<vector<int>> e(n);
        vector<int> r(n,0);
        for(int i=0;i<n;i++){
            if(nums[i]!=-1){
                e[nums[i]].push_back(i);
                r[i]++;
            }
        }
        string ans;
        priority_queue<int,vector<int>,greater<>> q;
        for(int i=0;i<n;i++){
            if(r[i]==0)
                q.push(i);
        }
        while(!q.empty()){
            int f=q.top();
            q.pop();
            for(int t:e[f]){
                r[t]--;
                if(r[t]==0)
                    q.push(t);
            }
            ans+=','+to_string(f);
        }
        return ans.substr(1);
    }
};

拓扑排序模板题，记录邻接表和入度表即可，使用优先队列做BFS，秒A

### 
import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串 
     * @return string字符串
     */
    public String compileSeq(String input){
        // write code here
        String[] items = input.split(",");
        int len = items.length;
        PriorityQueue queue = new PriorityQueue();
        int[] inDegree = new int[len];
        List[] adj = new ArrayList[len];
        for(int i = 0; i < len; ++i){
            adj[i] = new ArrayList();
        }
        for(int i = 0;i < len; ++i){
            int file = i;
            int depend = Integer.valueOf(items[i]);
            if(depend == -1){
                queue.add(i);
            }else{
                inDegree[i]++;
                adj[depend].add(file);
            }
        }
        int index = 0;
        List res = new ArrayList();
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            int head = queue.poll();
            res.add(String.valueOf(head));
            for(int file : adj[head]){
                inDegree[file]--;
                if(inDegree[file] == 0){
                    queue.add(file);
                }
            }
        }

        return String.join(",", res);
    }
}

使用的思路是拓扑排序，但这题单纯用拓扑排序只能通过80%,需要加入小根堆（可以先做LC课程表那题 ，思想几乎一模一样）

from collections import defaultdict
import heapq

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 编译顺序
# @param input string字符串
# @return string字符串
#
class Solution:
    def compileSeq(self, input):
        # write code here
        relationList = list(map(int, input.split(",")))
        inDegree = [0] * len(relationList)
        relationDict = defaultdict(list)
        for i in range(len(relationList)):
            if relationList[i] != -1:
                inDegree[i] += 1
                relationDict[relationList[i]].append(i)

        queue = []
        for i in range(len(inDegree)):
            if inDegree[i] == 0:
                heapq.heappush(queue,i)

        res = []
        while queue:
            cur = heapq.heappop(queue)
            res.append(cur)
            for item in relationDict[cur]:
                inDegree[item] -= 1
                if inDegree[item] == 0:
                    heapq.heappush(queue,item)
        return ",".join([str(e) for e in res])


if __name__ == "__main__":
    sol = Solution()
    print(sol.compileSeq("5,0,4,4,5,-1"))

js解法，用了深度优先搜索dfs，保存每次的结果，然后对结果重新排序

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 编译顺序
 * @param input string字符串 
 * @return string字符串
 */
function compileSeq( input ) {
     // write code here
    var input=input.split(',')

    // console.log(input)
    if (input.length===0) return
    var b=new Array(input.length)
    for(let i =0;i<b.length;i++){
        b[i]=false
        input[i]=parseInt(input[i])
    }
    var res=[]

    function dfs(i){

        if(input[i]===-1){
            temp.push(i)
            b[i]=true

            return temp
        }

        else if (input[i]!==-1){

            temp.unshift(input[i])
            b[input[i]]=true

            dfs(input[i])
        }

    }
    for(let i=0;i<input.length;i++){
        // console.log(b[input[i]])
        if (!b[i]){
            // console.log(i)

            var temp=[]
            temp.push(i)
            b[i]=true
            dfs(i,temp)
            // console.log(temp)
            res.push(temp)
            // console.log(res)
        }
    }
    // var r=res.join(',')
    // console.log(res)
    var r=[]
    var j=0;
    while(j <input.length){
        var t=[]
        for (let k=0;k<res.length;k++){
            t.push(res[k][0]) 
        }

        t.sort(function(a,b){return a-b;})
        // console.log(t)
        var m=t[0]

        r.push(m)
        for (let k=0;k<res.length;k++){
            res[k]=res[k].filter(function (value){return value !==m})
        }
        j=j+1
    }
    r=r.join(',')
    return r

}
module.exports = {
    compileSeq : compileSeq
};

拍个序就完事了搞什么优先队列，不要人云亦云。

from collections import defaultdict
class Solution:
    def compileSeq(self , input ):
        # write code here
        g = {}
        idg = defaultdict(int)
        lst = input.split(",")
        for i in range(len(lst)):
            g[i] = []
            idg[i] = 0
        # 图
        for i,v in enumerate(lst):
            if v != "-1":
                g[int(v)].append(i)
        # 入度
        for node in g:
            for nei_node in g[node]:
                idg[nei_node] += 1

        q = sorted([v for v in g if idg[v] == 0])
        res = []
        while q:
            q = sorted(q)
            node = q.pop(0)
            res.append(node)
            for nei in g[node]:
                idg[nei] -= 1
                if idg[nei] == 0:
                    q.append(nei)
        return ",".join(map(str, res))

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#include <sstream>
#include <set>
using namespace std;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串
     * @return string字符串
     */
    string compileSeq(string input) {
        // write code here
        unordered_multimap<int, int> m;
        queue<int> q;
        istringstream is;
        string res;
        is.str(input);
        int n = 0;
        int tmp;
        char c;
        is >> tmp;
        m.emplace(tmp, n++);
        while(is.get(c)){
            is >> tmp;
            m.emplace(tmp, n++);
        }
        tmp = -1;
        set<int> s;
        unordered_multimap<int, int>::iterator p;
        while(!m.empty() || !s.empty()){
            while(true){
                p = m.find(tmp);
                if(p == m.end())
                    break;
                s.emplace(p -> second);
                m.erase(p);
            }
            if(!s.empty()){
                tmp = *s.begin();
                q.push(tmp);
                s.erase(s.begin());
            }
        }
        ostringstream oss;
        while(!q.empty()){
            oss << q.front() << ',';
            q.pop();
        }
        res = oss.str();
        return res.substr(0, res.size() - 1);
    }
};

/*
 * dfs 拓扑排序
 */ 

#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

bool compare(int a, int b)
{
    return a > b;   //降序排列，如果改为return a<b，则为升序
}

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& adj) {
        vector<int> flags(numCourses, 0);
        vector<int> res(numCourses);
        res.clear();
        for (int i = numCourses - 1; i >= 0; i--) {
            //题目要求按数字升序排列，这里从数字大的节点开始dfs，因此在结果数组中的位置会更靠后（使用的是insert函数）
            if (!dfs(adj, flags, i, res)) return vector<int>();
        }
        return res;
    }
private:
    bool dfs(vector<vector<int>>& adj, vector<int>& flags, int i, vector<int>& res) {
        if (flags[i] == 1) return false;    //本次搜索来过此节点，说明存在环
        if (flags[i] == -1) return true;    //说明此点已经被其他点启动的dfs访问过，返回true
        flags[i] = 1;
        for (int j : adj[i]) {
            if (!dfs(adj, flags, j, res)) return false;
        }
        flags[i] = -1;
        res.emplace(res.begin(), i);        //将此点加入要返回的结果数组中
        return true;
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串
     * @return string字符串
     */
    string compileSeq(string input) {
        // write code here
        int i = 0;      //记录文件个数
        vector<int> nums;
        while (!input.empty()) {
            if (input.find(',') == string::npos) {
                nums.push_back(stoi(input));
                input.clear();
                i++;
                break;
            }
            string tmp = input.substr(0, input.find(','));
            nums.push_back(stoi(tmp));
            input.erase(0, input.find(',') + 1);
            i++;
        }
        vector<vector<int>> adj(i, vector<int>());      //前驱节点链表生成
        for (int j = 0; j < i; j++) {
            if (nums[j] == -1) continue;        //没有文件依赖的情况，跳过
            adj[nums[j]].push_back(j);
        }
        for (int j = 0; j < adj.size(); j++) {
            if (adj[j].size() >= 2) {
                sort(adj[j].begin(), adj[j].end(), compare);    //对每个结点的前驱结点进行升序排列，数字大的先进行dfs，在结果数组中的位置更靠后（使用insert函数），这样输出的时候才能按数字升序返回
            }
        }
        vector<int> res = findOrder(i, adj);    //使用dfs进行搜索
        string s;
        //输出
        for (int j = 0; j < i; j++) {
            s += to_string(res[j]);
            if (j < i - 1) {
                s.push_back(',');
            }
        }
        return s;
    }
};

答案集有个错的，本身这样写应该是正确的额。
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串
     * @return string字符串
     */
    string compileSeq(string input) {
        // write code here
        vector<int> result;
        string result1;
        stringstream s1(input);
 
        vector<int> v1;
        string temp;
        stringstream change;
        while (getline(s1, temp, ','))
        {
            int temp1;
            change << temp; change >> temp1;
            v1.push_back(temp1);
            change.clear();
        }
 
        int n = v1.size();
        for (int i = 0; i < n; i++)
        {
            if (v1[i] == -1)
            {
                result.push_back(i);
            }
        }
 
        bfs(v1, result);
 
        int length = result.size();
        for (int i = 0; i < length; i++)
        {
            int g = result[i];
            result1.append(to_string(g));
            if (i < length - 1) {
                result1.push_back(',');
            }
        }
        return result1;
    };
    void bfs(vector<int>& input, vector<int>& result)
    {
        int n = input.size();
        if (result.size() == input.size()) return;
        vector<int> curr;
        for (int i = 0; i < n; i++)
        {
            if ((input[i] != -1) && (input[input[i]] == -1))
            {
                result.push_back(i);
                curr.push_back(i);
            }
        }
        for (auto k : curr) input[k] = -1;
        bfs(input, result);
    }
};