现在有个工作流系统,包含了 nodes 和 edeges(点和边),运行这个工作流时需要按照顺序
来执行,举例:
上图中的执行顺序就是:输入->文本拆分->输出。现在简化输入的内容,每个节点只有节点
id,边只有两个 id,代表从 A->B 有一个先后执行的关系。请完成以下方法:
class NodeMap {
public int[] findOrder(int nodeCount, int[][] edges) {
}
}
其中 nodeCount 代表 node 数量(编号从 0 至 N-1),edges 代表了所有的边,输出为 node 执
行的顺序。
样例:
输入参数是:nodeCount=4, edges=[[0,1],[0,2],[3,0],[2,1]]
输出是:[3,0,2,1]
样例说明:
import cn.hutool.json.JSONUtil;
import java.util.*;
public class Test {
public static void main(String[] args) {
int[][] a = new int[4][2];
a[0] = new int[]{0,1};
a[1] = new int[]{0,2};
a[2] = new int[]{3,0};
a[3] = new int[]{2,1};
System.out.println(JSONUtil.toJsonStr(findOrder(4,a)));
}
public static int[] findOrder(int nodeCount, int[][] edges) {
//先找到起点
Map<Integer,Integer> head = new HashMap<>();
for (int[] edge:edges) {
//线起点个数
Integer num = head.get(edge[0]);
if (num == null){
head.put(edge[0],1);
} else {
head.put(edge[0],num+1);
}
}
Integer start = null;
for (Integer key:head.keySet()) {
if (head.get(key) == 1){
start = key;
}
}
//遍历线段后得到的路径
List<Integer> path = new ArrayList<>();
path = buildPath(path,edges,start);
//[3,0,0,1,0,2,2,1]
//逆序合并相同节点
List<String> list = new ArrayList<>();
int index = 0;
for (int j = path.size() -1;j>= 0 ; j-- ) {
if (!list.contains(path.get(j)+"")){
list.add(path.get(j)+"");
}
}
int k = 0;
int[] ret = new int[nodeCount];
for (int j = list.size() -1;j>= 0 ; j-- ) {
ret[k++] = Integer.valueOf(list.get(j));
}
return ret;
}
private static List<Integer> buildPath(List<Integer> path, int[][] edges, Integer start) {
//当前起点
for (int i = 0; i <edges.length ;i++) {
int[] edge = edges[i];
if (edge[0] == start){
path.add(edge[0]);
path.add(edge[1]);
buildPath(path,edges,edge[1]);
}
}
return path;
}
我是出题人,不要抄这份答案了,过不了简历关的