Java算法问题：输出两条连接路径中的一条

Question

/**
* The Problem:
*
* We have a list of tasks. Each task can depend on other tasks. 
* For example if task A depends on task B then B should run before A.
* 
* Implement the "getTaskWithDependencies" method such that it returns a list of task names in the correct order.
* 
* For example if I want to execute task "application A", the method should return a list with "storage,mongo,application A".
*
* List of Tasks:
*
*   - name: application A
*     dependsOn:
*       - mongo
*
*   - name: storage
*
*   - name: mongo
*     dependsOn:
*       - storage
*
*   - name: memcache
*
*   - name: application B
*     dependsOn:
*       - memcache
*
* The Java program is expected to be executed succesfully.
*/
public class Solution { 
 private static List<String> getTaskWithDependencies(List<Task> tasks, String dependsOn) {
   // TODO: please implement logic here
   
 }
  
  

 @Test
 public void testGetTaskDependenciesForApplicationA() {
   Assert.assertEquals(
     Arrays.asList(
       "storage",
       "mongo",
       "application A"
     ),
     getTaskWithDependencies(TaskList.getTasks(), "application A")
   );
 }
}

/**
* Definition of a Task
*/
class Task {
 private final String name;
 private final List<String> dependsOn;

 Task(String name) {
   this(name, new ArrayList<>());
 }

 Task(String name, List<String> dependsOn) {
   this.name = name;
   this.dependsOn = dependsOn;
 }

 public String getName() { return this.name; }
 public List<String> getDependsOn() { return this.dependsOn; }
}

class TaskList {
 public static List<Task> getTasks() {
   List<Task> tasks = new ArrayList<>();

   tasks.add(new Task("application A", Arrays.asList("mongo")));
   tasks.add(new Task("storage"));
   tasks.add(new Task("mongo", Arrays.asList("storage")));
   tasks.add(new Task("memcache"));
   tasks.add(new Task("application B", Arrays.asList("memcache")));

   return tasks;
 }
}

总体思路是给出一些方向关系，包括： 应用程序a->；mongodb->；这是一条连接路径 应用程序b->；memcache这是一条连接路径， 既然指定了应用程序A，就需要在其所在的位置输出连接的路径。 我的方法是使用拓扑排序将这5个点排序在一起。结果将是b->；memcache->；a->；mongo->；存储 我的问题是：如何只输出一条连接的路径而忽略另一条？我读到Leetcode中没有类似的问题，所以不知道。 我可以自己写代码，能告诉我这个想法很好

Answer 1

你可以使用递归来解决你的问题

从方法中传递的list of tasks中，通过task的name过滤，获取带有dependsOn的。如果task有自己的dependsOn列表，则迭代该列表，并调用递归函数，将相同的list of tasks和迭代字符串作为newDependsOn传递给它。将从递归函数获得的所有结果附加到一个逗号分隔的StringBuilder中，该StringBuilder带有一个","，它将用作生成最终列表的分隔符

完成所有这些迭代之后，将初始dependsOn附加到StringBuilder。最后，返回StrinBuilder.toStirng().split(",")as列表以获得最终结果

注意：我已经编写了代码，但根据您的要求，我还没有将其添加到这个答案中。如果你需要进一步的帮助，请在评论中询问我，如果需要，我会提供代码

更新

根据您的要求，我将添加以下代码：

private static List<String> getTaskWithDependencies(List<Task> tasks, String dependsOn) {
    StringBuilder resultString = new StringBuilder();
    Task task = tasks.stream().filter(x -> dependsOn.equalsIgnoreCase(x.getName())).findAny().get();
    if (task.getDependsOn() != null && !task.getDependsOn().isEmpty()) {
        for (String newDependsOn : task.getDependsOn()) {
            List<String> res = getTaskWithDependencies(tasks, newDependsOn);
            for (String ele : res) {
                resultString.append(ele).append(",");
            }
        }
    }
    resultString.append(dependsOn);
    return Arrays.asList(resultString.toString().split(","));
}

现在，如果使用以下命令运行代码：

public static void main(String[] args) {
    System.out.println(getTaskWithDependencies(TaskList.getTasks(), "application A"));
}

您将获得以下输出：

[storage, mongo, application A]