3
**給出一個字符串詞典[字符串都在有序]你必須要找到根據字典字符的優先級..查找字符的優先級在字典
吃
BXY
e爲根據字典上面的排名b!**
我試圖解決這個問題,用拓撲排序,並寫了下面的代碼,它給了我ebxyat的輸出。我無法確定我的解決方案,有什麼建議嗎? (這個問題在谷歌接受採訪時問)
public static ArrayList<Vertex> topologicalSort (List<Vertex> graph){
if (graph == null || graph.isEmpty()){
throw new IllegalArgumentException();
}
ArrayList<Vertex> result = new ArrayList<>();
for (Vertex v : graph){
if (!v.isVisited){
dfs(v,result);
}
}
return result;
}
public static void dfs (Vertex v, ArrayList<Vertex> result){
v.isVisited = true;
for (Vertex adjVertex : v.AdjList){
if (!adjVertex.isVisited){
dfs(adjVertex, result);
}
}
result.add(v);
}
public static void main(String[] args) {
List<Vertex> graph = new ArrayList<>();
Vertex p1 = new Vertex("e");
Vertex p2 = new Vertex("a");
Vertex p3 = new Vertex("t");
Vertex p4 = new Vertex("b");
Vertex p5 = new Vertex("x");
Vertex p6 = new Vertex("y");
p1.AdjList = Arrays.asList(new Vertex[]{p2, p4});
p2.AdjList = Arrays.asList(new Vertex[]{p3});
p3.AdjList = Arrays.asList(new Vertex[]{});
p4.AdjList = Arrays.asList(new Vertex[]{p5});
p5.AdjList = Arrays.asList(new Vertex[]{p6});
p6.AdjList = Arrays.asList(new Vertex[]{});
graph.add(p1);
graph.add(p2);
graph.add(p3);
graph.add(p4);
graph.add(p5);
graph.add(p6);
ArrayList<Vertex> compileOrder = topologicalSort(graph);
for(Vertex vertex : compileOrder){
System.out.println(vertex.data);
}
}
}
我不明白「優先級」是什麼意思。例如,與e和b相關的排名如何?你的意思是他們第一次出現的順序? –
我覺得按照字典的順序。 –
e的排名高於a,並且a的排名高於t,基本上是它們出現的順序。 –